凯德比赛当中ac率最高的题，然而还是卡了一天T^T 原因居然是读错题了→_→ 错把要求的方案数认为是走的步数orz当时算出来第三个示例不是7而是8的时候，就应该好好审题，不应该只纠结于“0”的问题，真要是比赛可怎么办？？细心点吧

/*********
根据是否走过的标记 避免一直在“0”
而且很符合回溯的思想
2015.12.17
196K	204MS	C++	1383B
*********/
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char str[44][44];
int map[44][44],vis[44][44];
__int64 dp[44][44];
int n;
int dirx[2] = {0,1};
int diry[2] = {1,0};
void init() {
    memset(dp,0,sizeof(dp));
    memset(map,0,sizeof(map));
    memset(vis,0,sizeof(vis));
}

bool inside(int i,int j) {
    if(i<0 || i>=n || j<0 || j>=n) return false;
    return true;
}

__int64 dfs(int x,int y) {
    if(dp[x][y] != 0) {
      //  cout << x << ' ' << y << ' ' << dp[x][y] << endl;
        return dp[x][y];
    }
    if(x == n-1 && y == n-1) return 1;
    for(int i=0; i<2; i++) {
        int xx=x+dirx[i]*map[x][y];
        int yy=y+diry[i]*map[x][y];
        if(inside(xx,yy)&&!vis[xx][yy])
        {
            vis[xx][yy]=1;
            dp[x][y]+=dfs(xx,yy);
            vis[xx][yy]=0;
        }
    }
   // cout << x << ' ' << y << ' ' << dp[x][y] << endl;
    return dp[x][y];
}

int main() {
    //freopen("cin.txt","r",stdin);
    int i,j;
    while(scanf("%d",&n)) {
        if(n == -1) break;
        init();
        for(i=0; i<n; i++) {
            scanf("%s",str[i]);
        }
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                map[i][j] = str[i][j] - '0';
            }
        }
        vis[0][0] = 1;
        printf("%I64d\n",dfs(0,0));

    }
    return 0;
}