Minesweeper algorithm in C++[KOI 2020]

I'm preparing KOI 2022, so, I'm solving KOI 2021, 2020 problems. KOI 2020 contest 1 1st period problem 5(See problem 5 in here)

I want to make <vector<vector<int>> minesweeper(vector<vector<int>> &v) function that works on 5*5 minesweeper.

argument

vector<vector<int>> &v

Numbers in minesweeper that converted to vector. -1 if it is blank.

e.g. {{0, 0, 1, -1, 1}, {-1, 3, 3, -1, 1}, {-1, -1, -1, -1, 0}, {2, 5, -1, 3, -1}, {-1, -1, -1, -1, -1}}

return value

A vector. Size is same with argument. Mine is 1, default is 0.

English translation of KOI 2020 contest 1 1st period problem 5

There is a 5*5 minesweeper puzzle.

There are 11 numbers, and the others are blank.

0	0	1	가	1
나	3	3		1
			다	0
2	5		3
	라			마

Where is the mine?

A. 가

B. 나

C. 다

D. 라

E. 마

How can I make minesweeper function? I want algorithm description, too.

Solution

There two some simple rules to solving Minesweeper:

If a field sees all it's mines then all blank fields don't have mines and can be uncovered.
If a field has as many blank fields as it is missing mines then they all contain mines.

Keep applying those rules over and over till nothing changes.

Now it gets complex because you have to look at combinations of fields. Instead of figuring out lots of special cases for 2, 3, 4 known fields I suggest going straight to a brute force algorithm:

For every blank field next to a know field:

create copies of the map with a mine present and not present
go back to the top to solve each map
if one of the maps results in any known field to not see enough mines then the other case must be the actual solution, apply it and go back to the start

If no progress was made then you have to guess. The above loop can give you probabilities for where mines are and if you know the number of mines total you have a probability for other blank fields. Pick one least likely to have a mine.