AOJ 0156 Moats around the Castle

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156。

解法

天守閣からBFS、複数続いている堀をその度にカウントしてWAを出していた。

コード

nt dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0};

int main(){
  int n, m, i, j, d, res;
  while(scanf("%d%d", &n, &m) && n+m){
    char cas[128][128];
    int cnt[128][128];
    rep(i, m) rep(j, n) cnt[i][j] = INF;
    rep(i, m) scanf("%s", cas[i]);

    int x, y;
    rep(i, m) rep(j, n) if(cas[i][j] == '&'){ y = i; x = j;}
    cnt[y][x] = 0;
    cas[y][x] = '.';
    queue<pi>q;
    q.push(make_pair(y, x));
    while(!q.empty()){
      int qsize = (int)q.size();
      rep(i, qsize){
    pi now = q.front(); q.pop();

    rep(d, 4){
      int ny = now.Y + dy[d], nx = now.X + dx[d];
      if(ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
      int cost = cnt[now.Y][now.X] + ((cas[ny][nx] == '#' && cas[now.Y][now.X] == '.') ? 1 : 0);
      if(cnt[ny][nx] <= cost) continue;
      cnt[ny][nx] = cost;
      q.push(make_pair(ny, nx));
    }
      }
    }

    res = INF;
    rep(i, m){
      res = min(res, cnt[i][0]);
      res = min(res, cnt[i][n-1]);
    }
    rep(i, n){
      res = min(res, cnt[0][i]);
      res = min(res, cnt[m-1][i]);
    }
    printf("%d\n", res);
  }
  return 0;
}