鱼C论坛

 找回密码
 立即注册
查看: 3820|回复: 1

跪求大佬看一下,迷宫问题解决不了

[复制链接]
发表于 2019-3-26 00:48:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
一天蒜头君掉进了一个迷宫里面,蒜头君想逃出去,可怜的蒜头君连迷宫是否有能逃出去的路都不知道。
看在蒜头君这么可怜的份上,就请聪明的你告诉蒜头君是否有可以逃出去的路。
输入格式
第一行输入两个整数
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
  1. #include<iostream>
  2. using namespace std;
  3. char mp[15][15];
  4. int vis[15][15];
  5. int m,n;
  6. int s[4][2]={ {0,1},{-1,0},{0,-1},{1,0} };
  7. bool in(int i,int j){
  8.     return ( 0<=i && i<m && 0<=j && j<n );
  9. }
  10. int dfs(int i,int j){
  11.     if( mp[i][j]=='T' ) return 1;
  12.     vis[i][j]=1;
  13.     for(int k=0;k<4;k++){
  14.         int nx=i+s[k][0]; int ny=j+s[k][1];
  15.         if( in(nx,ny) && vis[nx][ny]==0  && mp[nx][ny]!='*' )
  16.             dfs(nx,ny);
  17.     }
  18.     return 0;
  19. }
  20. int main(){
  21.     int x,y;
  22.     cin >> m >> n;
  23.     for(int i=0;i<m;i++)
  24.         for(int j=0;j<n;j++)
  25.             cin >> mp[i][j];
  26.     for(int i=0;i<m;i++)
  27.         for(int j=0;j<n;j++)
  28.             if(mp[i][j]=='S'){
  29.                  x=i; y=j;
  30.                  break;
  31.             }
  32.     if( dfs(x,y) )    cout << "yes" << endl;
  33.     else              cout << "no" << endl;
  34.     return 0;
  35. }
复制代码

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2019-3-26 04:42:36 | 显示全部楼层
本帖最后由 Croper 于 2019-3-26 04:58 编辑

楼主的题目看不清,我反正默认迷宫同一行输入时无空格了

我用的广度优先,感觉写着要舒服一点

  1. //这里,迷宫是以vector<string>的形式组织的,每个string代表迷宫的一行。

  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <string>
  6. using namespace std;

  7. struct location {
  8.         int x;
  9.         int y;
  10. };

  11. location MazeFindStart(const vector<string>& Maze) {  //获取迷宫出发点
  12.         for (int j = 0; j < Maze.size(); ++j) {
  13.                 for (int i = 0; i < Maze[j].size(); ++i) {
  14.                         if (Maze[j][i] == 'S') {
  15.                                 return { i,j };
  16.                         }
  17.                 }
  18.         }
  19.         return { -1,-1 };
  20. }

  21. inline bool LocationInMaze(location loc, const vector<string>& Maze) {               //判断一个点是否在迷宫内
  22.         return (loc.y >= 0 && loc.y < Maze.size() && loc.x>=0 && loc.x < Maze[loc.y].size());
  23. }

  24. bool MazzHasExit(vector<string>& Maze) {                 //主要函数:判断迷宫是否有出口
  25.         queue<location> que;                                      //使用队列保存需要判断的位置,这里是广度优先;深度优先把queue换成stack就行                                                                                       
  26.         location startloc = MazeFindStart(Maze);
  27.         que.push(startloc);                                          //把开始点加入队列

  28.         while (!que.empty()) {                                     //开始遍历,
  29.                 location loc = que.front();                        
  30.                 que.pop();

  31.                 if (!LocationInMaze(loc, Maze)) continue;     //如果点不在迷宫内,那么移除此点
  32.                 char &c = Maze[loc.y][loc.x];                     
  33.                 if (c == 'T') return true;                              //如果点是出口,那么迷宫有出口,直接返回ture
  34.                 if (c == '.' || c=='S') {                              
  35.                         c = 'p';                                              //如果是可通行路径,那么把此点标记为'p'(已经经过),并把此点的相邻点加入队列
  36.                         que.push({ loc.x - 1,loc.y });               //*这里偷了一点懒,为了少写几行代码,在加入临近点时没有做任何判断,而是把判断反在了当点从队列里取出时,但是同一个点可能反复进出队列,降低效率;
  37.                         que.push({ loc.x + 1,loc.y });
  38.                         que.push({ loc.x,loc.y-1 });
  39.                         que.push({ loc.x,loc.y+1 });
  40.                 }                                                             //其他情况(点是墙/点为已经经过的路径),那么移除此点
  41.         }
  42.         return false;                                           //如果队列为空仍然没有找到出口,那么就说明找不到出口
  43. }

  44. int main() {
  45.         int m, n;
  46.         vector<string> Maze;

  47.         cin >> m >> n;
  48.         Maze.resize(m);

  49.         for (int j = 0; j < n; ++j) {
  50.                 cin >> Maze[j];
  51.         }

  52.         if (MazzHasExit(Maze)) {
  53.                 cout << "yes" << endl;
  54.         }
  55.         else {
  56.                 cout << "no" << endl;
  57.         }

  58.         system("pause");
  59. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 11:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表