/*
分析:
简单DP。
flag[][]表示可以到达改点的方法数。
刚开始:
外循环扫描所有点flag[x][y],而内循环扫描出所有可以到达
点x、y的点i、l。
那么flag[x][y]就是所有的flag[i][l]之和。
写的时候就感觉会超时,还真超了- -I。原因很简单么,因为对于
每个x、y点,都要把所有的i<x&&l<y的点都扫描一遍,而好多情况根本
就不用扫描的,因为0<=e<=20;再说况且对于100*100的二维表格,数据
量会很大。
所以,应该将扫描的方式变一下:
外循环扫描所有的[i][l]点,并将flag[i][l]加到[i][l]可达
的点的flag上即可。
不过我的方法优化后也是187MS,谁有更好的方法欢迎讨论O(∩_∩)O哈!
2012-04-24
*/
#include"stdio.h" #include"string.h" int main() { int flag[111][111]; //方法数。 int num[111][111]; int T; int n,m; int i,l; int x,y; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) for(l=0;l<m;l++) scanf("%d",&num[i][l]); memset(flag,0,sizeof(flag)); flag[0][0]=1; for(i=0;i<n;i++) { for(l=0;l<m;l++) { if(i==n-1&&l==m-1) continue; flag[i][l]%=10000; for(x=i;x<=num[i][l]+i&&x<n;x++) { for(y=l;y<=num[i][l]+l&&y<m;y++) { if(x==i&&y==l) continue; if(num[i][l]>=x-i+y-l) { flag[x][y]+=flag[i][l]; //优化,把这行换个地儿。 flag[x][y]%=10000; 优化前203MS,优化后187MS。 } } } } } flag[n-1][m-1]%=10000; printf("%d\n",flag[n-1][m-1]); } return 0; }