Minesweeper Game I

Minesweeper is a classic single-player game. Players need to use known information to judge whether unknown squares are mines and mark the positions of the mines in a grid.

In this challenge, you are given three parameters: width, height, and mineCount. Please write an algorithm to generate the initial map for a Minesweeper game, which is a 2D array with width rows and height columns. There should be mineCount mines randomly placed on the map.

Requirement: Your algorithm must be uniformly random. That is, every square has the same probability of being a mine ($P(x) = \frac{mineCount}{width \times height}$).

Try to implement this algorithm. Click the "Submit" button to generate a Minesweeper map with your algorithm and have fun!

Advanced

First question: What is the time complexity and space complexity of your random algorithm? Can you make the space complexity $O(mineCount)$?

Second question: How do you prove your random algorithm is uniformly random? How can you prove that each cell has the same probability of being chosen?

Explanation