题目：在一个N*M的网格中，从左上角走到右下角，有一些点不能经过，求最短路的条数。
分析：dp，帕斯卡三角。每一个点最短的就是走N条向下，M条向右的路。
到达每一个点的路径条数为左边和上面的路径之和。
说明：注意数据输入格式。
#include#include #include #include using namespace std;int smap[101][101];int sums[101][101];int temp[101];int getnumber(int tem[], char str[]){ int move = 0,save = 0; while (str[move]) { while (str[move] < '0' || str[move] > '9') { if (!str[move]) return save; move ++; } int value = 0; while (str[move] >= '0' && str[move] <= '9') { value *= 10; value += str[move ++]-'0'; } tem[save ++] = value; } return save;}int main(){ int T,N,M; char buf[1001]; scanf("%d",&T);getchar(); while (T --) { scanf("%d%d",&N,&M);getchar(); memset(smap, 0, sizeof(smap)); memset(sums, 0, sizeof(sums)); for (int i = 1 ; i <= N ; ++ i) { gets(buf); int count = getnumber(temp, buf); for (int i = 1 ; i < count ; ++ i) smap[temp[0]][temp[i]] = 1; } sums[1][1] = 1; for (int i = 2 ; i <= N && !smap[i][1] ; ++ i) sums[i][1] = 1; for (int i = 2 ; i <= M && !smap[1][i] ; ++ i) sums[1][i] = 1; for (int i = 2 ; i <= N ; ++ i) for (int j = 2 ; j <= M ; ++ j) { sums[i][j] = sums[i-1][j]+sums[i][j-1]; if (smap[i][j]) sums[i][j] = 0; } printf("%d\n",sums[N][M]); if (T) printf("\n"); } return 0;}