北京外包公司 网站开发,中国可信网站查询,wordpress用户注册设置,网站设计网站开发题目描述 一个由n * m 个格子组成的迷宫#xff0c;起点是(1, 1)#xff0c; 终点是(n, m)#xff0c;每次可以向上下左右四个方向任意走一步#xff0c;并且有些格子是不能走动#xff0c;求从起点到终点经过每个格子至多一次的走法数。 输入 第一行一个整数T 表示有T 组…题目描述 一个由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 0 2 2 0 1 1 0 2 3 0 0 0 0 0 0 示例输出 1 0 4 #includeiostream
#includecstdio
#include cstring
#includecstdlib
#includecmath
#includealgorithm
using namespace std;
int mp[7][7],vis[7][7];
int sum,m,n;
void Dfs(int x,int y)找能走到xy的通路
{if(x1||xn||y1||ym||mp[x][y]1)return;//递归结束的条件if(xnym){sum;//找到一条通路return;}if(vis[x][y]0){vis[x][y]1;//走不通Dfs(x1,y);Dfs(x,y1);Dfs(x-1,y);Dfs(x,y-1);//访遍四周vis[x][y]0;}
}
int main()
{int t;scanf(%d,t);while(t--){sum0;memset(vis,0,sizeof(vis));//对数组vis的初始化都为0scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j)scanf(%d,mp[i][j]);}Dfs(1,1);//找能走到最后的通路printf(%d\n,sum);}
}
