C++实现简单的走迷宫 一时失言乱红尘 2022-06-17 07:58 151阅读 0赞 **c++实现简单走迷宫** 用n\*n个小方格代表迷宫,每个方格上有一个字符0或1,0代表这个格子不能走,1代表这个格子可以走。只能一个格子一个走,而且只能从一个格子向它的上、下、左、右四个方向走,且不能重复。迷宫的入口和出口分别位于左上角和右下角,存在唯一的一条路径能够从入口到达出口,试着找出这条路径。 例如,下图是一个迷宫,红色表示走出迷宫的一条路径 ![Center][] 输入:入口坐标(startX,startY),出口坐标(endX,endY) 输出:如果存在这样一条路径,则输出1,并输出路径(0,0)->(1,0)->(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)->(5,5)->(4,5)->(4,6)->(4,7)->(5,7)->(6,7)->(7,7) **思路:利用回溯法求解。** **首先,根据输入在矩阵中找到路径的起点。假设矩阵中某个格子的字符为1,就往相邻的格子寻找字符为1的格子。** **除了在矩阵边界上的格子之外,每个格子都有4个相邻的格子。重复这个过程直到在矩阵中找到相应的出口位置。** **当在矩阵中定位了路径上n个格子的位置后,在与第n个格子周围都没有找到第n+1个格子为1,则只好在路径上回到第n-1个格子,重新去寻找第n个字符为1的格子** **由于路径不能重复进入格子,我们需要定义一个字符矩阵一样大小的布尔值矩阵,用来标记路径是否已经进入了相应格子。** **代码实现如下:** #include <iostream> #include <vector> using namespace std; class Solution { public: bool hasPath(char* matrix, int rows, int cols, int startX,int startY, int endX, int endY,vector<int>& Path) { if (matrix == NULL || rows < 1 || cols < 1 || startX<0||startY<0||endX<0||endY<0||(startX==endX&&startY==endY)) return false; bool* visited = new bool[rows*cols]; //定义一个辅助矩阵,用来标记路径是否已经进入了每个格子 memset(visited, 0, rows*cols); int pathLength = 0; if (hasPathCore(matrix, rows, cols, startX, startY, endX, endY, visited, Path)) { return true; } delete[] visited; return false; } /*此函数用来判断在当前路径满足条件下,相邻格子中是否存在一个格子满足条件*/ bool hasPathCore(char* matrix, int rows, int cols, int row, int col, int endX, int endY, bool* visited, vector<int>& Path) { if ((row == endX) && (col == endY)&&(matrix[row*cols+col]=='1')) { Path.push_back(endY); Path.push_back(endX); return true; } bool hasPath = false; if (row >= 0 && row < rows&&col >= 0 && col < cols&&matrix[row*cols + col] == '1' && !visited[row*cols + col]) { // ++pathLength; visited[row*cols + col] = true; Path.push_back(col); Path.push_back(row); /*如果矩阵格子(row,col)字符为1时,从它的4个相邻格子中寻找下一个字符为1的格子*/ hasPath = hasPathCore(matrix, rows, cols, row, col - 1, endX, endY, visited,Path) || hasPathCore(matrix, rows, cols, row - 1, col, endX, endY, visited,Path) || hasPathCore(matrix, rows, cols, row, col + 1, endX, endY, visited,Path) || hasPathCore(matrix, rows, cols, row + 1, col, endX, endY, visited,Path); if (!hasPath) //如果没找到,则说明当前第n个格子定位不正确,返回上一个位置重新定位 { visited[row*cols + col] = false; Path.pop_back(); Path.pop_back(); } } return hasPath; } }; int main() { // char* matrix = "abcesfcsadee"; char* matrix = "1000000110110001101000010111011110100000010000001"; //设置迷宫 int startX, startY, endX, endY; cin >> startX >> startY >> endX >> endY; //输入起始结束坐标 Solution s; vector<int> Path; bool re = s.hasPath(matrix, 7, 7, startX,startY,endX,endY,Path); cout << re << endl; for (int i = 0; i < Path.size();) cout << "(" << Path[i++] << ',' << Path[i++] << ")" << " "; cout << endl; return 0; } [Center]: /images/20220617/f91991b351f44009adc40a5d59feb193.png
相关 C语言实现小游戏:走迷宫 走迷宫: 1、定义一个二维数组作为迷宫 2、定义老鼠的坐标 3、获取游戏开始时的时间time(NULL) 4、进入循环 1、system 清理屏幕 2、 ╰半夏微凉°/ 2022年12月15日 14:22/ 0 赞/ 183 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终 向右看齐/ 2022年09月25日 11:21/ 0 赞/ 177 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终 喜欢ヅ旅行/ 2022年09月25日 11:20/ 0 赞/ 139 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 超、凢脫俗/ 2022年07月12日 13:10/ 0 赞/ 156 阅读
相关 走迷宫 Problem Description 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是 深藏阁楼爱情的钟/ 2022年07月12日 07:14/ 0 赞/ 176 阅读
相关 走迷宫 Problem Description 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是 我不是女神ヾ/ 2022年07月12日 07:14/ 0 赞/ 152 阅读
相关 走迷宫 think: 1题目似乎没有很明显的模板性,我是否应该反思转换学习图的方法,自己目前的认识水平这个题目很难找到DFS与BFS的影子,自己应该把思维延伸,将DFS与BFS的思 港控/mmm°/ 2022年07月12日 07:05/ 0 赞/ 162 阅读
相关 C++实现简单的走迷宫 c++实现简单走迷宫 用n\n个小方格代表迷宫,每个方格上有一个字符0或1,0代表这个格子不能走,1代表这个格子可以走。只能一个格子一个走,而且只能从一个格子向它的 一时失言乱红尘/ 2022年06月17日 07:58/ 0 赞/ 152 阅读
相关 走迷宫 通过栈将每次可以通过的路径保存起来。 但是要注意关于入口点和出口点的一些边界问题 一不小心就可能因为边界问题陷入死循环或者程序直接崩溃。 pragma war 傷城~/ 2022年06月17日 07:12/ 0 赞/ 148 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 秒速五厘米/ 2022年06月10日 12:25/ 0 赞/ 156 阅读
还没有评论,来说两句吧...