跪求大佬看一下，迷宫问题解决不了
一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。
输入格式
第一行输入两个整数
nn
n 和
mm
m，表示这是一个
n×mn \times m
n×m 的迷宫。
接下来的输入一个
nn
n 行
mm
m 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。
输出格式
输出一个字符串，如果蒜头君可以逃出迷宫输出"yes"，否则输出"no"。
数据范围
1≤n,m≤101 \le n, m \le 10
1≤n,m≤10。
输出时每行末尾的多余空格，不影响答案正确性
样例输入1
复制
3 4
S**.
..*.
***T
样例输出1
复制
no
样例输入2
复制
3 4
S**.
....
***T
样例输出2
复制
yes#include<iostream>
using namespace std;
char mp;
int vis;
int m,n;
int s={ {0,1},{-1,0},{0,-1},{1,0} };
bool in(int i,int j){
return ( 0<=i && i<m && 0<=j && j<n );
}
int dfs(int i,int j){
if( mp=='T' ) return 1;
vis=1;
for(int k=0;k<4;k++){
int nx=i+s; int ny=j+s;
if( in(nx,ny) && vis==0&& mp!='*' )
dfs(nx,ny);
}
return 0;
}
int main(){
int x,y;
cin >> m >> n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin >> mp;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(mp=='S'){
x=i; y=j;
break;
}
if( dfs(x,y) ) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
本帖最后由 Croper 于 2019-3-26 04:58 编辑
楼主的题目看不清，我反正默认迷宫同一行输入时无空格了
我用的广度优先，感觉写着要舒服一点
//这里，迷宫是以vector<string>的形式组织的，每个string代表迷宫的一行。
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
struct location {
int x;
int y;
};
location MazeFindStart(const vector<string>& Maze) {//获取迷宫出发点
for (int j = 0; j < Maze.size(); ++j) {
for (int i = 0; i < Maze.size(); ++i) {
if (Maze == 'S') {
return { i,j };
}
}
}
return { -1,-1 };
}
inline bool LocationInMaze(location loc, const vector<string>& Maze) { //判断一个点是否在迷宫内
return (loc.y >= 0 && loc.y < Maze.size() && loc.x>=0 && loc.x < Maze.size());
}
bool MazzHasExit(vector<string>& Maze) { //主要函数：判断迷宫是否有出口
queue<location> que; //使用队列保存需要判断的位置，这里是广度优先；深度优先把queue换成stack就行
location startloc = MazeFindStart(Maze);
que.push(startloc); //把开始点加入队列
while (!que.empty()) { //开始遍历，
location loc = que.front();
que.pop();
if (!LocationInMaze(loc, Maze)) continue; //如果点不在迷宫内，那么移除此点
char &c = Maze;
if (c == 'T') return true; //如果点是出口，那么迷宫有出口，直接返回ture
if (c == '.' || c=='S') {
c = 'p'; //如果是可通行路径，那么把此点标记为'p'(已经经过），并把此点的相邻点加入队列
que.push({ loc.x - 1,loc.y }); //*这里偷了一点懒，为了少写几行代码，在加入临近点时没有做任何判断，而是把判断反在了当点从队列里取出时，但是同一个点可能反复进出队列，降低效率；
que.push({ loc.x + 1,loc.y });
que.push({ loc.x,loc.y-1 });
que.push({ loc.x,loc.y+1 });
} //其他情况（点是墙/点为已经经过的路径），那么移除此点
}
return false; //如果队列为空仍然没有找到出口，那么就说明找不到出口
}
int main() {
int m, n;
vector<string> Maze;
cin >> m >> n;
Maze.resize(m);
for (int j = 0; j < n; ++j) {
cin >> Maze;
}
if (MazzHasExit(Maze)) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
system("pause");
}
页:
[1]