2013年8月28日

UVa 825 - Walking on the Safe Side

#include <cstdio>
#include <sstream>
using namespace std;

int main() {
  char s[999];
  gets(s);
  int T;
  sscanf(s, "%d", &T);
  gets(s);
  while (T--) {
    gets(s);
    int R, C;
    sscanf(s, "%d%d", &R, &C);
    int dp[101][101] = {};
    while (gets(s) && s[0]) {
      istringstream ss(s);
      int r, c;
      ss >> r;
      while (ss >> c) {
        dp[r][c] = -1;
      }
    }
    dp[1][1] = 1;
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        if (r && dp[r][c] != -1 && dp[r - 1][c] != -1) {
          dp[r][c] += dp[r - 1][c];
        }
        if (c && dp[r][c] != -1 && dp[r][c - 1] != -1) {
          dp[r][c] += dp[r][c - 1];
        }
      }
    }
    printf("%d\n", dp[R][C]);
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言