http://acm.hdu.edu.cn/showproblem.php?pid=1208
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 100 5 #define ll __int64 6 using namespace std; 7 8 ll dp[maxn][maxn]; 9 char g[maxn][maxn]; 10 int a[maxn][maxn]; 11 int n; 12 13 ll dfs(int x,int y) 14 { 15 int xx,yy; 16 if(dp[x][y]||(!a[x][y])) return dp[x][y]; 17 xx=x+a[x][y]; 18 yy=y; 19 if(xx>=0&&xx<n&&yy>=0&&yy<n) 20 { 21 dp[x][y]+=dfs(xx,yy); 22 } 23 xx=x; 24 yy=y+a[x][y]; 25 if(xx>=0&&xx<n&&yy>=0&&yy<n) 26 { 27 dp[x][y]+=dfs(xx,yy); 28 } 29 return dp[x][y]; 30 } 31 32 int main() 33 { 34 while(scanf("%d",&n)!=EOF) 35 { 36 if(n==-1) break; 37 for(int i=0; i<n; i++) 38 { 39 scanf("%s",g[i]); 40 for(int j=0; j<n; j++) 41 { 42 a[i][j]=g[i][j]-'0'; 43 } 44 } 45 memset(dp,0,sizeof(dp)); 46 dp[n-1][n-1]=1; 47 printf("%I64d ",dfs(0,0)); 48 } 49 return 0; 50 }