11142 - MineSweeper II

[arsalan_mousavian]

i've got many WA on this problem , can somebody post some IO ?
i think my program works for following testcases

Code: Select all

5
4 3 6
1..
2..
2..
...
4 3 7
1..
2..
2..
...
5 5 25
.....
.....
.....
.....
.....
1 3 1
1..
1 3 2
1..

Code: Select all

Case #1:
1..
2..
2X.
...
Case #2:
1XX
2.X
2XX
..X
Case #3:
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
Case #4:
1X.
Case #5:
1XX

thanks in Advance
Arsalan

[Jan]

I think your input cases are not correct. I havent solved it yet but I am giving some cases.
Input:

Code: Select all

2
3 3 2 
1.. 
2.. 
2..
1 3 1 
1..

Output:

Code: Select all

Case #1:
1.. 
2X. 
2X.
Case #2:
1X.

Hope it helps.

[arsalan_mousavian]

my program handles your Cases ( because they are much easier than mine ), which input is incorrect ? all of them are valid ,

[arsalan_mousavian]

can't anybody help me ?

[rammestain]

I'm getting TLE, please give me hint

[Vexorian]

I've been getting a lot of WAs on this one, I think I increased the WA count from 100 to 141. But anyways, my current input deals with a lot of cases but I have a problem and it is that the statement does not make it clear what to do with ambiguous input, it says that all the input will be valid but it doesn't mention ambiguous data.

It says that all the squares that certainly have a mine must be replaced with an X

With that logic this :

Code: Select all

4 3 7
1..
2..
2..
...

would become this:

Code: Select all

1.X
2.X
2.X
..X

Those 4 squares are the only ones that we are certain they have a square, but I am not too sure about this and I just can't stop getting WA. Would appreciate if the problemsetter or a person who got AC replies., cause I am pretty clueless on how to deal with these cases.

[arsalan_mousavian]

few months ago that i was in the mood for solving this problem, i've got many WAs
i think the only solutions are

Code: Select all

1XX
2.X
2XX
X.X

1XX
2.X
2XX
.XX

the only way you can put 7 bombs on the board, and i don't think there will be another valid solution with 7 bombs for this map,

[Vexorian]

I see then this solution is the correct one IF we follow that logic.

Code: Select all

1XX
2.X
2XX
..X 

But I am still not sure and even you had WA so some confirmation would be nice

[arsalan_mousavian]

as in my input it is mentioned that there will be 7 bombs in the map then your solution is completely wrong,

[sclo]

I got accepted and here's more input, and a hint:

we never need to check any unmarked cells that are more than a distance 1 away from any marked cells. If the number of these unmarked cells is equal to the number of bombs remaining, then mark all of these unmarked cells to be bombs. As for the unmarked cells that are adjacent to a marked cell, we need to do backtracking to generate all possible placement of bombs.

input:

Code: Select all

15
4 3 6
1..
2..
2..
...
4 3 7
1..
2..
2..
...
1 3 1
1..
1 3 2
1.. 
3 3 2
121
...
...
3 3 5
..2
...
2.2
3 3 5
121
...
...
3 3 4
..3
...
2.2
3 3 5
..3
...
2.2
4 4 10
....
.8..
....
2..1
4 4 9
....
.8..
....
2..1
4 3 1
...
.E.
...
1..
4 3 2
...
.E.
...
1..
3 3 9
...
...
...
3 3 8
...
...
... 

Output:

Code: Select all

Case #1:
1..
2..
2X.
...
Case #2:
1XX
2.X
2XX
..X
Case #3:
1X.
Case #4:
1XX
Case #5:
121
X.X
...
Case #6:
XX2
X.X
2X2
Case #7:
121
X.X
XXX
Case #8:
.X3
XXX
2.2
Case #9:
XX3
XXX
2.2
Case #10:
XXXX
X8XX
XXX.
2..1
Case #11:
XXX.
X8X.
XXX.
2..1
Case #12:
...
.E.
...
1X.
Case #13:
...
.E.
...
1XX
Case #14:
XXX
XXX
XXX
Case #15:
...
...
...

[those]

Here is my thinking.
One possible solution for handling some of the unmarked cells which are not adjacent to any "numbers" is that after filling all the bombs needed beside the "numbers", if the number of remaining cells that are away from the "numbers" equal to the number of bombs left, mark all of them.

However, I think it is very difficult to handle this kind of input.

Code: Select all

3 3 6
1..
...
...

I know what should be output, but it's just not easy to handle this.

Can anyone give me any idea to handle this kind of input?