2013年8月2日

UVa 11352 - Crazy King

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

typedef pair<int, int> P;
const int dr[8] = {1, 2, 1, 2, -1, -2, -1, -2};
const int dc[8] = {2, 1, -2, -1, 2, 1, -2, -1};

int main() {
  int T;
  char s[99];
  gets(s);
  sscanf(s, "%d", &T);
  while (T--) {
    int M, N;
    gets(s);
    sscanf(s, "%d%d", &M, &N);
    bool block[100][100] = {};
    P start, end;
    for (int r = 0; r < M; r++) {
      gets(s);
      for (int c = 0; s[c]; c++) {
        if (s[c] == 'A') {
          start = MP(r, c);
          block[r][c] = true;
        } else if (s[c] == 'B') {
          end = MP(r, c);
        } else if (s[c] == 'Z') {
          block[r][c] = true;
          for (int i = 0; i < 8; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < M && nc >= 0 && nc < N) {
              block[nr][nc] = true;
            }
          }
        }
      }
    }
    block[end.first][end.second] = false;
    queue<P> q;
    q.push(start);
    bool find = false;
    int dis[100][100] = {};
    while (!q.empty()) {
      P now = q.front();
      int r = now.first, c = now.second;
      int d = dis[r][c];
      q.pop();
      if (now == end) {
        printf("Minimal possible length of a trip is %d\n", d);
        find = true;
        break;
      }
      for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
          if (!i && !j) {
            continue;
          }
          int nr = r + i, nc = c + j;
          if (nr >= 0 && nr < M && nc >= 0 && nc < N && !block[nr][nc]) {
            q.push(MP(nr, nc));
            dis[nr][nc] = d + 1;
            block[nr][nc] = true;
          }
        }
      }
    }
    if (!find) {
      puts("King Peter, you can't go now!");
    }
  }
  return 0;
}

沒有留言:

張貼留言