I have Wa#4. Please help me!
#input
5 5
ooooo
ooooo
ooooo
ooooo
ooooo
2
1
13
#output
???

Can you give me a hint with test #41?

I pass all tests, that I think up. Can anybody give me more tests???

i think these one car can't came from south,
because point #4 is most southern. There is no
point to the south of a point number 4.

please explain me sample input, i don't understand

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

Would anybody tell me how looks test 42 (or what's the trick) ?

Why the sample output is:
Experiment #1: North: 0, South: 1, East: 0, West: 0

And what does it mean?
"Assume that the checkpoints are numbered bottom-up and from left to right."

Did somebody have any trouble whith this test? I just can't pas it. Thanks in advance.

The algo is O(W*H*M) - the only BFS for each experiment in fact. By the way, Memory Limit it too huge. My program on Pascal uses 3399 Kb only.

is there something special about this problem's output ?