欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa 825 - Walking on the Safe Side

程序员文章站 2022-04-02 19:01:09
...

题目:在一个N*M的网格中,从左上角走到右下角,有一些点不能经过,求最短路的条数。

分析:dp,帕斯卡三角。每一个点最短的就是走N条向下,M条向右的路。

            到达每一个点的路径条数为左边和上面的路径之和。

说明:注意数据输入格式。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio> 

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;
}