2013年8月28日

UVa 926 - Walking Around Wisely

#include <cstdio>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int sr, sc, er, ec;
    scanf("%d%d%d%d", &sc, &sr, &ec, &er);
    int W;
    scanf("%d", &W);
    bool block[33][33][2] = {};
    while (W--) {
      int r, c;
      char d[9];
      scanf("%d%d%s", &c, &r, d);
      switch (*d) {
        case 'N':
          block[r][c][0] = true;
          break;
        case 'E':
          block[r][c][1] = true;
          break;
        case 'S':
          block[r - 1][c][0] = true;
          break;
        case 'W':
          block[r][c - 1][1] = true;
          break;
      }
    }
    long long dp[33][33] = {}; // key : long long
    dp[sr][sc] = 1;
    for (int r = sr; r <= er; r++) {
      for (int c = sc; c <= ec; c++) {
        if (!block[r - 1][c][0]) {
          dp[r][c] += dp[r - 1][c];
        }
        if (!block[r][c - 1][1]) {
          dp[r][c] += dp[r][c - 1];
        }
      }
    }
    printf("%lld\n", dp[er][ec]);
  }
  return 0;
}

沒有留言:

張貼留言