POJ 2704

 1 #include <iostream>
 2 #include <string>
 3 #define LL long long
 4 #define MAXN 100
 5 using namespace std;
 6 
 7 int dis[2][2] = {1,0,0,1};
 8 
 9 int _m[MAXN][MAXN];
10 LL dp[MAXN][MAXN];
11 struct node
12 {
13     int x;
14     int y;
15 };
16 int n;
17 LL dfs(node _node);
18 //bool mark[MAXN][MAXN];
19 int main()
20 {
21     //freopen("acm.acm","r",stdin);
22 
23     int i;
24     int j;
25     string s;
26     while(cin>>n)
27     {
28         getchar();
29         if(n == -1)
30         {
31             break;
32         }
33         memset(dp,0,sizeof(dp));
34         for(i = 0; i < n; ++ i)
35         {
36             getline(cin,s);
37             for(j = 0; j < n; ++ j)
38             {
39                 //cin>>_m[i][j];
40                 _m[i][j] = s[j]-'0';
41             }
42         }
43     
44         node b;
45         b.x = 0;
46         b.y = 0;
47         cout<<dfs(b)<<endl;
48     }
49 }
50 
51 
52 LL dfs(node _node)
53 {
54     if(_node.x == n-1 && _node.y == n-1)
55     {
56         return 1;
57     }
58     if(_m[_node.x][_node.y] == 0)
59     {
60         return 0;
61     }
62     node temp;
63     temp.x = _node.x+_m[_node.x][_node.y];
64     temp.y = _node.y;
65     if(temp.x < n)
66     {
67         if(dp[temp.x][temp.y] == 0)
68         {
69             dp[_node.x][_node.y] += dfs(temp);
70         }
71         else
72         {
73             dp[_node.x][_node.y] += dp[temp.x][temp.y];
74         }
75     }    
76     temp.x = _node.x;
77     temp.y = _node.y+_m[_node.x][_node.y];
78     if(temp.y < n)
79     {
80         if(dp[temp.x][temp.y] == 0)
81         {
82             dp[_node.x][_node.y] += dfs(temp);
83         }
84         else
85         {
86             dp[_node.x][_node.y] += dp[temp.x][temp.y];
87         }
88     }
89 
90     return dp[_node.x][_node.y];
91 }