题目描述
数据结构实验之栈与队列十：走迷宫
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
一个由n * m 个格子组成的迷宫，起点是(1, 1)， 终点是(n, m)，每次可以向上下左右四个方向任意走一步，并且有些格子是不能走动，求从起点到终点经过每个格子至多一次的走法数。
Input
第一行一个整数T 表示有T 组测试数据。(T <= 110)
对于每组测试数据:
第一行两个整数n, m，表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行，每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走，否则是1 表示这个格子不能走，输入保证起点和终点都是都是可以走的。
任意两组测试数据间用一个空行分开。
Output
对于每组测试数据，输出一个整数R，表示有R 种走法。
Sample Input
3
2 2
0 1
0 0
2 2
0 1
1 0
2 3
0 0 0
0 0 0
Sample Output
1
0
4
分析 & 代码
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<memory.h>
#include<iostream>
using namespace std;
int t;
int n,m;
int mmap[7][7]; //保存地图信息
int vis[7][7]; //标记是否已经走过
int fx[] = {0,0,-1,1}; //四个方向
int fy[]= {1,-1,0,0};
int num;
int judge(int x, int y){ //判断某个点是否可以走 条件有 1.是否已经走过 2.地图可走 3.不是边界
if(vis[x][y]==0 && mmap[x][y]==0 && x>=1 && x <=n && y>=1 && y<= m){
return 1;
}
return 0;
}
void dfs(int x, int y){
if(x==n && y==m){ //每次走到终点就记录加一
num++;
}
vis[x][y] = 1; //标记已经走过
for(int i=0; i<4; i++){
if(judge(x+fx[i], y+fy[i])){
//vis[x+fx[i]][y+fy[i]] = 1;
dfs(x+fx[i], y+fy[i]);
vis[x+fx[i]][y+fy[i]] = 0; //每次递归结束 再将这个点置为未走过 方便下一次使用
}
}
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
num=0;
memset(vis, 0, sizeof(vis));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++)
cin>>mmap[i][j];
}
dfs(1, 1);
cout<<num<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116789.html
