华为OJ迷宫问题

旧城等待， 2022-06-17 00:54 168阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">定义一个二维数组N*M（其中2&lt;=N&lt;=10;2&lt;=M&lt;=10），如5&nbsp;×&nbsp;5数组下所示：&nbsp; int&nbsp;maze[5][5]&nbsp;=&nbsp;{
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0,&nbsp;1,&nbsp;0,&nbsp;0,&nbsp;0, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0,&nbsp;1,&nbsp;0,&nbsp;1,&nbsp;0, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0,&nbsp;0,&nbsp;0,&nbsp;0,&nbsp;0, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0,&nbsp;1,&nbsp;1,&nbsp;1,&nbsp;0, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0,&nbsp;0,&nbsp;0,&nbsp;1,&nbsp;0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。Input一个N&nbsp;×&nbsp;M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。Output左上角到右下角的最短路径，格式如样例所示。Sample&nbsp;Input0&nbsp;1&nbsp;0&nbsp;0&nbsp;00&nbsp;1&nbsp;0&nbsp;1&nbsp;00&nbsp;0&nbsp;0&nbsp;0&nbsp;00&nbsp;1&nbsp;1&nbsp;1&nbsp;00&nbsp;0&nbsp;0&nbsp;1&nbsp;0Sample&nbsp;Output(0,&nbsp;0)(1,&nbsp;0)(2,&nbsp;0)(2,&nbsp;1)(2,&nbsp;2)(2,&nbsp;3)(2,&nbsp;4)(3,&nbsp;4)(4,&nbsp;4) &nbsp;&nbsp;&nbsp;</pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 查找,搜索,排序</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 左上角到右下角的最短路径，格式如样例所示。 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 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</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> (0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <string> 
 #include <vector>
 #include <algorithm>
 #include <map>
 #include <deque>
 //#include "Customer.h"
 using namespace std;
 
 struct Point
 {
 	int x;
 	int y;
 };
 int mat[100][100] = { 0 };
 int N, M;
 deque<Point> path;
 deque<Point> minPath;
 
 //判断当前点是否可行
 bool correct(int i, int j)
 {
 	if ((i >= 1 && i <= N) && (j >= 1 && j <= M) && mat[i][j] == 0)
 		return true;
 	else
 		return false;
 }
 //采用回溯法解决迷宫最短路径问题，遍历所有可行路径path，minPath保存最短路径
 void visit(int i, int j)
 {
 	mat[i][j] = 2;
 	Point pt;
 	pt.x = i;
 	pt.y = j;
 	path.push_back(pt);
 	if (i == N && j == M)
 	{
 		if (minPath.empty() || path.size() < minPath.size())
 		{
 			minPath.assign(path.begin(), path.end());
 		}
 		mat[i][j] = 0;
 		path.pop_back();
 		return;
 	}
 
 	if (correct(i - 1, j))
 	{
 		visit(i - 1, j);
 	}
 	if (correct(i + 1, j))
 	{
 		visit(i + 1, j);
 	}
 	if (correct(i, j - 1))
 	{
 		visit(i, j - 1);
 	}
 	if (correct(i, j + 1))
 	{
 		visit(i, j + 1);
 	}
 
 	mat[i][j] = 0;
 	path.pop_back();
 }
 int main()
 {
 
 	cin >> N >> M;
 	for (int i = 1; i <= N; i++)
 	{
 		for (int j = 1; j <= M; j++)
 			cin >> mat[i][j];
 	}
 
 	visit(1, 1);
 	for (int i = 0; i < minPath.size(); i++)
 		cout << "(" << minPath[i].x-1 << "," << minPath[i].y -1<< ")" << endl;
 	return 0;
 }