题目
迷宫有一个入口，一个出口。一个人从入口走进迷宫，目标是找到出口。阴影部分和迷宫的外框为墙，每一步走一格，每格有四个可走的方向，探索顺序为地图方向：南（下）、东（右）、北（上）、西（左）。
输入：输入迷宫数组。第一行数据表示一个 n*n (n<=100)的迷宫；第二行开始的n行为迷宫数据。
其中：0表示路，1表示墙，起点在左上角 <1,1> 的位置，终点在右下角 <n,n> 的位置。
输出：若有解，输出从入口到出口的一条路径，否则输出 there is no solution!
例（上图所示的迷宫数组）
输入：
4 4
0 0 1 0
0 1 0 1
0 0 0 0
0 1 0 0
输出：<1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4>
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
C++代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAX_N = 100;
int maze[MAX_N][MAX_N]; // 定义迷宫数组
bool visited[MAX_N][MAX_N]; // 记录访问过的位置
int n; // 迷宫大小
int dx[4] = { 1, 0, -1, 0 }; // 南、东、北、西的移动方向
int dy[4] = { 0, 1, 0, -1 }; // 南、东、北、西的移动方向
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
// 检查当前位置是否可以访问
bool isValid(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 0 && !visited[x][y]);
}
// 深度优先搜索函数，寻找从起点到终点的路径
bool dfs(int x, int y, vector<Point>& path) {
if (x == n - 1 && y == n - 1) { // 检查是否到达终点
path.push_back(Point(x + 1, y + 1)); // 调整为1索引输出
return true;
}
visited[x][y] = true; // 标记当前位置为已访问
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny)) {
path.push_back(Point(x + 1, y + 1)); // 调整为1索引输出
if (dfs(nx, ny, path)) {
return true;
}
path.pop_back();
}
}
return false;
}
int main() {
cin >> n>>n; // 输入迷宫大小
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> maze[i][j]; // 输入迷宫数据
}
}
vector<Point> path;
if (dfs(0, 0, path)) { // 调用深度优先搜索
for (const Point& p : path) {
cout << "<" << p.x << "," << p.y << "> "; // 输出路径
}
cout << endl;
}
else {
cout << "There is no solution!" << endl; // 输出无解
}
}
