题目大意：给出一个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;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。