題目： UVA - 825Walking on the Safe Side(dp)
題目大意：給出一個n * m的矩陣，起點是1 * 1，終點是n * m，這個矩陣上有些點是不可以經過的，要求從起點到終點距離最短，並且不能走那種不能走的點，一共有多少種方式。
解題思路：要求路徑最短的話，每個點要不向右走，要不向下走。dp【i】【j】 = dp【i】【j + 1】 + dp【i + 1】【j】；當這個點不能通過，dp【i】【j】 = 0；這個坑點在樣例輸入，不一定是規范的輸入，可能兩個數字之間很多空格，或者最後一個數字和換行符之間很多空格。
代碼：
#include#include const int N = 1005; typedef long long ll; int G[N][N]; ll dp[N][N]; char str[N]; void handle () { int x, y; bool flag = 1; x = y = 0; // printf ("%s\n", str); for (int i = 0; i <= strlen (str); i++) { if (str[i] >= '0' && str[i] <= '9') { if (flag) x = x * 10 + str[i] - '0'; else y = y * 10 + str[i] - '0'; } else { if (!flag) G[x][y] = 1; // printf ("%d %d\n", x, y); y = 0; flag = 0; } } } int main () { int t, n, m; int x, y; char ch; scanf ("%d", &t); while (t--) { scanf ("%d%d%*c", &n, &m); memset (G, 0, sizeof (G)); for (int i = 1; i <= n; i++) { gets(str); handle(); } for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) { dp[i][j] = 0; if (G[i][j]) continue; if (i == n && j == m) { dp[i][j] = 1; continue; } if (i != n) dp[i][j] += dp[i + 1][j]; if (j != m) dp[i][j] += dp[i][j + 1]; } printf ("%lld\n", dp[1][1]); if (t) printf ("\n"); } return 0; }
