http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2449
1 #include<stdio.h> 2 #include<string.h> 3 const int N=520; 4 int vis[N][N],map[N][N]; 5 int n,m,cnt; 6 void dfs(int x,int y) 7 { 8 if (x==n&&y==m) 9 { 10 cnt++; 11 return ; 12 } 13 if (x-1>=1&&map[x-1][y]==0&&!vis[x-1][y]) 14 { 15 vis[x][y] = 1; 16 dfs(x-1,y); 17 vis[x][y] = 0; 18 } 19 if (x+1<=n&&map[x+1][y]==0&&!vis[x+1][y]) 20 { 21 vis[x][y] = 1; 22 dfs(x+1,y); 23 vis[x][y] = 0; 24 } 25 if (y-1>=1&&map[x][y-1]==0&&!vis[x][y-1]) 26 { 27 vis[x][y] = 1; 28 dfs(x,y-1); 29 vis[x][y] = 0; 30 } 31 if (y+1<=m&&map[x][y+1]==0&&!vis[x][y+1]) 32 { 33 vis[x][y] = 1; 34 dfs(x,y+1); 35 vis[x][y] = 0; 36 } 37 } 38 int main() 39 { 40 int t; 41 scanf("%d",&t); 42 while(t--) 43 { 44 cnt = 0; 45 scanf("%d%d",&n,&m); 46 memset(vis,0,sizeof(vis)); 47 for (int i = 1; i <= n; i ++) 48 { 49 for (int j = 1; j <= m; j ++ ) 50 { 51 scanf("%d",&map[i][j]); 52 } 53 } 54 vis[1][1] = 1; 55 dfs(1,1); 56 printf("%d ",cnt); 57 } 58 return 0; 59 } 60