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
