Post
by **Jucovschi Constantin** » Wed Nov 27, 2002 7:23 pm

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.