2195.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2195 on 2006-04-02 at 22:44:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int MAX = 36;

int main()
{
	int64 path[MAX][MAX];
	int n, i, j;
	
	while(scanf("%d", &n) != EOF && n > 0) {
		memset(path, 0, sizeof(path)); path[0][0] = 1;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				int step; scanf("%1d", &step);
				if(step == 0) continue;
				int cx = i + step, cy = j + step;
				if(cx < n) path[cx][j] += path[i][j];
				if(cy < n) path[i][cy] += path[i][j];
			}
		printf("%lld\n", path[n-1][n-1]);
	}
	
	return 0;
}