2013年8月28日

UVa 11067 - Little Red Riding Hood

#include <cstdio>

int main() {
  int R, C;
  while (scanf("%d%d", &C, &R) && R) {
    int n, dp[101][101] = {1};
    scanf("%d", &n);
    while (n--) {
      int r, c;
      scanf("%d%d", &c, &r);
      dp[r][c] = -1;
    }
    for (int r = 0; r <= R; r++) {
      for (int c = 0; 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];
        }
      }
    }
    if (dp[R][C] <= 0) {
      puts("There is no path.");
    } else if (dp[R][C] == 1) {
      puts("There is one path from Little Red Riding Hood's house to her grandmother's house.");
    } else {
      printf("There are %d paths from Little Red Riding Hood's house to her grandmother's house.\n", dp[R][C]);
    }
  }
  return 0;
}

沒有留言:

張貼留言