QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB

# 5317. Winmine.exe

Statistics

Notes

(a) The upper bound of w (the number of mines) should be 1500, rather than 1000 in the problem statement.

(b) There is another (the third) constraint about the initial state of board: for any pair of unrevealed squares A and B, if A and B are both adjacent to a connected component S, where S is a connected area consisting of only squares with positive positive positive positive numbers, then A and B can always be connected by unrevealed squares. For example, the following board contradicts this constraint due to the disconnection of squares on row 7 column 3 and row 8 column 4:

000000011.
11000001..
.1000002..
11000001..
0000000111
0111000000
01.3221100
012....100
0012221100
1100001110
.100001.10

, whereas the following one is acceptable:

..10000000
2210011100
000001.100
000001.100
000011.221
00001.....
01122.....
12........
..........
..........