2013年8月26日

UVa 10102 - The path in the colored field

#include <cstdio>
#include <queue>
#include <algorithm>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    char map[111][111];
    for (int r = 0; r < n; r++) {
      scanf("%s", map[r]);
    }
    int ans = 0;
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < n; c++) {
        if (map[r][c] == '1') {
          queue<P> q;
          int dis[111][111] = {};
          q.push(MP(r, c));
          while (!q.empty()) {
            P now = q.front();
            int d = dis[now.first][now.second];
            q.pop();
            if (map[now.first][now.second] == '3') {
              ans = max(ans, d);
              break;
            }
            for (int i = 0; i < 4; i++) {
              int nr = now.first + dr[i], nc = now.second + dc[i];
              if (0 <= nr && nr < n && 0 <= nc && nc < n && !dis[nr][nc]) {
                dis[nr][nc] = d + 1;
                q.push(MP(nr, nc));
              }
            }
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言