从起点出发,只能向右、向下、向左、向上移动一个方格,黑色方格为障碍物,不能通过。
求到达终点的最短路径,并输出最短路径。
![](/static/upload/1614327654121504.png)
【输入样例】
5 2 3
0 0 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 1
【输出样例】
<0,0> <0,1> <0,2> <1,2> <1,3> <2,3>
【参考程序】
//爱码岛编程
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int adj[105][105];
int visited[105][105];
struct Point {
int x;
int y;
Point *pre;
};
queue<Point *> que;
vector<Point *> path;
int n, endP, endQ;
void bfs(Point *p) {
que.push(p);
visited[p->x][p->y] = 1;
while (!que.empty()) {
p = que.front();
path.push_back(p);
int i = p->x;
int j = p->y;
que.pop();
if (i == endP && j == endQ) {
return;
}
// 4个邻居结点
if (adj[i][j + 1] == 0 && !visited[i][j + 1] && j + 1 < n) { //向右
Point *tp = new Point{i, j + 1, path.back()};
que.push(tp);
visited[i][j + 1] = 1;
}
if (adj[i + 1][j] == 0 && !visited[i + 1][j] && i + 1 < n) { //向下
Point *tp = new Point{i + 1, j, path.back()};
que.push(tp);
visited[i + 1][j] = 1;
}
if (adj[i][j - 1] == 0 && !visited[i][j - 1] && j - 1 > 0) { //向左
Point *tp = new Point{i, j - 1, path.back()};
que.push(tp);
visited[i][j - 1] = 1;
}
if (adj[i - 1][j] == 0 && !visited[i - 1][j] && i - 1 > 0) { //向上
Point *tp = new Point{i - 1, j, path.back()};
que.push(tp);
visited[i - 1][j] = 1;
}
}
}
void visit() {
vector<Point *> tmpPath;
Point *endPoint = path[path.size() - 1];
tmpPath.push_back(endPoint);
Point *cur = endPoint->pre;
while (cur != NULL) {
tmpPath.push_back(cur);
cur = cur->pre;
}
reverse(tmpPath.begin(), tmpPath.end());
for (int i = 0; i < tmpPath.size(); i++) {
cout << "<" << tmpPath[i]->x << "," << tmpPath[i]->y << "> ";
}
}
int main() {
cin >> n >> endP >> endQ;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> adj[i][j];
}
}
// BFS
Point *p = new Point{0, 0, NULL};
bfs(p);
//访问
visit();
return 0;
}