Please, give me some tests or hints.
Problem is easy...
Only BFS, nothing more.
But WA #17 (even after hours of debuging and testing)
My code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 503
#define MAX2 (MAX * MAX)
char S[MAX][MAX];
int N = 0, H, W, M, D[MAX][MAX], To[MAX][MAX];
int X[MAX2], Y[MAX2], Qx[MAX2], Qy[MAX2];
int Po, Si, Num[MAX];
int Co( int x, int y )
{
return 0 <= x && x < W && 0 <= y && y < H && (S[y][x] == '#' || S[y][x] == 'o');
}
int main( void )
{
int i, j, k, m, x, y, d, to, x1, y1;
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
scanf("%d%d", &W, &H);
for (i = 0; i < H; i++)
scanf("%s", S[i]);
for (i = H - 1; i >= 0; i--)
for (j = 0; j < W; j++)
if (S[i][j] == 'o')
X[++N] = j, Y[N] = i;
scanf("%d", &M);
for (m = 1; m <= M; m++)
{
scanf("%d", &k);
memset(D, -1, sizeof(D));
Po = 0, Si = 0, D[Y[k]][X[k]] = 0;
for (i = 0; i < 4; i++)
if (Co(x = X[k] + dx[i], y = Y[k] + dy[i]))
D[y][x] = 1, To[y][x] = i, Qx[Si] = x, Qy[Si++] = y;
while (Po < Si)
{
x = Qx[Po], y = Qy[Po++], d = D[y][x] + 1, to = To[y][x];
for (i = 0; i < 4; i++)
if (Co(x1 = x + dx[i], y1 = y + dy[i]))
if (D[y1][x1] == -1 || (D[y1][x1] == d && To[y1][x1] > to))
{
if (D[y1][x1] == -1)
Qx[Si] = x1, Qy[Si++] = y1;
D[y1][x1] = d, To[y1][x1] = to;
}
}
memset(Num, 0, sizeof(Num));
for (i = 1; i <= N; i++)
if (i != k && D[Y[i]][X[i]] != -1)
Num[To[Y[i]][X[i]]]++;
printf("Experiment #%d: North: %d, South: %d, East: %d, West: %d\n",
m, Num[1], Num[0], Num[3], Num[2]);
}
return 0;
}
Edited by author 25.01.2006 13:14
No overflow, so there is a mistake in BFS...
But where is it???
I also have WA#17 and can't find mistake in my program. May be we don't understand the problem.
There is no mistke in BFS, but in using BFS.
"Priorities acts" means that if car can turn for South and for North it turns for South. I had WA #17 too, because I thought that car chooses the side from that it comes to checkpoint. Try this test:
7 7
###....
#.#....
#.#.###
#.#.o.#
#.###.#
o.....#
#######
1
1
The answer is:
Experiment #1: North: 1, South: 0, East: 0, West: 0
Thank you! I'll fix my bag.
(wwwwww - my old login)