10381 - The Rock

[Jucovschi Constantin]

Hi. When I submit my program it gets WA. Can somebody check whether my program gives the correct answer for the following tests? Are there any tricky tests? Id appreciate any tests for checking my program

Code: Select all

3
5 18
X..#.#............
.#.....##..#....#.
..#..#.#..#.#..#..
.#.##.##.#...##...
.....E............

8 8
E.......
###.###.
........
.###.###
........
#######.
........
X#######

10 10
E.........
..........
..........
..........
..........
..........
..........
..........
..........
.........X


My outputs:
33
29
18

Thanks in advance

[jingye]

sigh. I get the same results as you. My program is WA also, though. Second test case will not occur because there are not two disjoint paths.

[Yarin]

The result of the first and last input is correct, but the second one is not a valid input. If your program actually gets an answer for that in any case, it's a bit strange, it should be infinite or something in that case.

There are no tricks in the problem nor the input really.

[jingye]

Finally got accepted.
I thought E stood for exit, lol.

To Jucovschi Constantin: My program will also output 29 for the second test case, so I guess we use the same method.

[Jucovschi Constantin]

I tried to get my program accepted but I couldnt.

I will write my idea, maybe it is wrong.

Consider the path consists of positions a1, a2, a3, .. an with a1=entrance. Suppose we delete position ai (it is the unknown wall) we have to reconstruct the path as a1, a2, a3 .. a(i-1) b1 b2 .. an. Sure b1, b2, .., an has to be the minimal path to connect a(i-1) and an with assumption that ai is a wall.

With F(i) we denote the length of the path that was reconstructed according the principle above.

The cost of a path is defined as max(F(i), i=1..n)

Let Q(x,y) be the minimal cost of all paths connecting the entrance with the position (x,y). |Q(x,y)| be the length of the path that gives this minimal cost.

Now if we take a neighbor position of (x,y), let it be (x1, y1). We can calculate the Q(x1,y1) = max(Q(x,y), |Q(x,y)|+minimal distance from (x,y) to exit).

The real algorithm is like djikstras algorithm. It takes minimal Q(x,y). And then tries to update the neighbors as it was shown.

Q(exit.x, exit.y) will be the optimal result.

I think it should work.

[jingye]

I use the exact same idea, except I begin Dijkstra from end and go to start. Maybe you can change your program, and try the opposite direction.

[CC]

can somebody give me the results for the following test cases

Code: Select all

10

20 40
........................................
........................................
........................................
........................................
.............###.#.#.#..................
............#...#.#...#.................
...........#..#.#.....#.................
...........#.#.X#......#................
...........#..#....#..#.................
............#......#...#................
.............###.##...#.................
................#.#...#.................
................#.#.#.#.................
...............#...#...#................
..............#....#....#...............
..............#....#....................
.....................#..................
......................#.................
.#####################.###############..
...................E....................

21 40
........................................
........................................
........................................
........................................
.............###.#.#.#..................
............#...#.#...#.................
...........#..#.#.....#.................
...........#.#.X#......#................
...........#..#....#..#.................
............#......#...#................
.............###.##...#.................
................#.#...#.................
................#.#.#.#.................
...............#...#...#................
..............#....#....#...............
..............#....#....................
.....................#..................
......................#.................
..####################.###############..
........................................
...................E....................

8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..

8 8
..X.....
........
##.##...
..#.....
##.##...
##.##...
........
..E.....
3 3
X..
...
..E
 
3 4
..X.
.#..
.E..
 
3 4
..X.
....
.E..

4 5
.....
.....
..#..
.E#X.

3 3
X..
.#.
..E

[Per]

My solution says:

Code: Select all

96
79
15
11
15
4
5
3
10
8

[Moha]

I got WA in this problem, in my algorithm, for each empty cell I compute the shortest path cost in which if I come to this cell from side i(0<=i<=3) and I see this cell is blocked, then I should change my way in order to not to go to this cell and sum of these two cost should be minimized. after computing all of these costs, I use a simple dijkstra to find the best path with changed updating rule. my code answer all of these posted test cases correctly but I got WA. can anybody help me or post some more test cases?