admin 管理员组

文章数量: 887021

A

A - 迷宫问题

前言：
最近感觉脑子不够用，一个水题也能想好久。头发倒掉不少，这是脑子跟着一起入冬了么。。。

题目：
定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

思路：
思路不难可直接看代码，题目主要需要有一个vector来记录走过的结点

AC代码：

#include "iostream"
#include "vector"
using namespace std;
int book[5][5];class Node{
public:int x;int y;Node(int x, int y) : x(x), y(y) {}
};
vector<Node*>path_temp;
vector<Node*>path_best;// 判断是否越界或者结点已访问
bool judge(int i, int j) {if (i<0 || j<0)return false;if (i>=5 || j>=5)return false;if (book[i][j]==1)return false;return true;
}void MazeTrack(int i = 0, int j = 0) {if (!judge(i,j))return;book[i][j] = 1;// 标记为已走过path_temp.push_back(new Node(i,j));if (i==4 && j==4){ // 如果到了终点if (path_best.empty() || path_temp.size()<path_best.size()){path_best = path_temp;}}MazeTrack(i-1,j);MazeTrack(i+1,j);MazeTrack(i,j-1);MazeTrack(i,j+1);book[i][j] = 0; // 恢复状态path_temp.pop_back();
}int main(){for (int i = 0; i < 5; ++i) {for (int j = 0; j < 5; ++j) {cin>>book[i][j];}}MazeTrack();for (int i = 0; i < path_best.size(); ++i) {cout<<'('<<path_best[i]->x<<", "<<path_best[i]->y<<")"<<endl;}
}

如果觉得有帮助就点个赞吧，没帮助的话隔壁的文章可能更好噢

本文标签： A

版权声明：本文标题：A 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686548851h8886.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。