UVA - 825 Walking on the Safe Side (dp)

제목의 뜻: n, m을 제시하고 현재 n줄을 제시한다. 줄마다 k(k는 정해지지 않은 값)의 숫자가 있다. 첫 번째 숫자는 줄의 수를 대표하고 뒤에 있는 k-1개의 수는 현재 줄의 이 위치를 대표하며 갈 수 없다. (1, 1)에서 (n, m)까지 몇 개의 경로가 있는지 물어보고 아래로 또는 오른쪽으로만 갈 수 있다.
해석: 이 가장 짧은 경로는 반드시 현재 행렬의 행 + 열이고 dp[i][j]수 그룹은 각 칸에 몇 가지 상황을 저장하는 데 사용되며 dp[i+1][j]+=dp[i][j];dp[i][j+1] += dp[i][j];

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctype.h>
using namespace std;
const int N = 200;
int w,n;
int grid[N][N];
int dp[N][N];
char str[N];

int main() {
	int T;
	int x,y;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&w,&n);
		memset(grid,0,sizeof(grid));
		
		y = 0;
		for(int i = 1; i <= w; i++) {
			scanf("%d",&x);
			gets(str);
			int len = strlen(str);
			for(int i = 0; i <= len; i++) {
				if(isalnum(str[i])) {
					y = y * 10 + (str[i] - '0');
				}else {
					grid[x][y] = true;
					y = 0;
				}
			}
		}
		memset(dp,0,sizeof(dp));
		dp[1][1] = 1;
		for(int i = 1; i <= w; i++) {
			for(int j = 1; j <= n; j++) {
				if(!grid[i][j]) {
					dp[i+1][j] += dp[i][j];
				}
				if(!grid[i][j]) {
					dp[i][j+1] += dp[i][j];
				}
			}
		}
		printf("%d
",dp[w][n]);
		if(T) {
			printf("
");
		}
	}
	return 0;
}