迷宫
时间限制:1000 ms | 内存限制:65535 KB
难度:4描述
一个由 n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每个格子至多一次的走法数。输入
第一行一个整数 T 表示有 T 组测试数据。(T <= 110) 对于每组测试数据: 第一行两个整数 n, m,表示迷宫有 n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来 n 行,每行 m 个数。其中第 i 行第 j 个数是 0 表示第 i 行第 j 个格子可以走,否则是 1 表示这个格子不能走,输入保证起点和终点都是都是可以走的。任意两组测试数据间用一个空行分开。 输出 对于每组测试数据,输出一个整数 R,表示有 R 种走法。 样例输入 3 2 2 0 1 0 02 2
0 1 1 02 3
0 0 0 0 0 0样例输出
1 0 4 #include#include int a[10][10];int n,m;int sum; //统计 可行的方案void dfs(int i,int j){ if(i<0||j<0||j>m-1||i>n-1||a[i][j])//控制边界 和 不能走的地方 return ; if(i==n-1&&j==m-1)//是否到达了终点 { sum++; return ; } a[i][j]=1;//标记走过的位置 dfs(i-1,j); //向上下左右走 dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); a[i][j]=0;//将刚刚标记的位置标记为0 }int main(){ int i,j,k,l; scanf("%d",&l); while(l--) { sum=0; scanf("%d %d",&n,&m); memset(a,0,sizeof(a)); for(i=0;i