Page 1 of 1
11142 - MineSweeper II
Posted: Sun Oct 29, 2006 4:11 pm
by 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
Posted: Sun Oct 29, 2006 10:57 pm
by Jan
I think your input cases are not correct. I havent solved it yet but I am giving some cases.
Input:
Output:
Hope it helps.
Posted: Sun Oct 29, 2006 11:28 pm
by arsalan_mousavian
my program handles your Cases ( because they are much easier than mine
), which input is incorrect ? all of them are valid ,
Posted: Mon Oct 30, 2006 1:30 pm
by arsalan_mousavian
can't anybody help me ?
Posted: Mon Oct 30, 2006 9:28 pm
by rammestain
I'm getting TLE, please give me hint
Posted: Mon Dec 18, 2006 8:49 pm
by 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 :
would become this:
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.
Posted: Mon Dec 18, 2006 11:49 pm
by 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
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,
Posted: Tue Dec 19, 2006 12:12 am
by Vexorian
I see then this solution is the correct one IF we follow that logic.
But I am still not sure and even you had WA so some confirmation would be nice
Posted: Tue Dec 19, 2006 8:37 pm
by arsalan_mousavian
as in my input it is mentioned that there will be 7 bombs in the map then your solution is completely wrong,
Posted: Sun Feb 11, 2007 11:57 pm
by 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:
...
...
...
Posted: Sat Mar 24, 2007 4:33 pm
by 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.
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?
