首页 > 代码库 > 数据结构之 栈与队列--- 走迷宫（深度搜索dfs）
数据结构之 栈与队列--- 走迷宫（深度搜索dfs）
走迷宫
Time Limit: 1000MS Memory limit: 65536K
题目描述
一个由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 种走法。
示例输入
32 20 10 02 20 11 02 30 0 00 0 0
示例输出
104
#include <iostream>#include <string>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;unsigned int map[6][6];bool vis[6][6];int dir[4][2]={{0, -1}, {0, 1}, {1, 0}, {-1, 0} }; //四个深搜的方向int cnt; //记录方法数int n, m;void dfs(int x, int y){ int i, j; int xx, yy; for(i=0; i<4; i++) { xx=x+dir[i][0]; yy=y+dir[i][1]; //进行了一次位置的转移 if( xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]==0 && vis[xx][yy]==false ) //如果可以走 { if(xx==n-1 && yy==m-1) { cnt++; continue; } else { vis[xx][yy]=true; //标记该点已走 dfs(xx, yy); //从当前点出发继续向四个方向dfs vis[xx][yy]=false; //当从该点的dfs结束之后，要将该点标记为未走状态， //因为可能会有其它的路径要经过该点，但是如果不标记， //就会造成死循环 } } }}int main(){ int t; cin>>t; int i, j; while(t--) { cin>>n>>m; cnt=0; for(i=0; i<n; i++) { for(j=0; j<m; j++) { cin>>map[i][j]; vis[i][j]=false; } } vis[0][0]=true; dfs(0, 0); cout<<cnt<<endl; } return 0;}
数据结构之 栈与队列--- 走迷宫（深度搜索dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。