include[HTML_REMOVED]
using namespace std;
const int N = 200;
int n,m;
int d[N][N];//存储从起点到各点的最短距离,初始化为-1,表示未访问过。
int g[N][N];//存储地图信息,0表示可以通过的点,非0表示有障碍物的点。
queue[HTML_REMOVED]> q; //用于BFS搜索的队列,存储点的坐标。
pair[HTML_REMOVED] prevNode[N][N]; //存储每个点的前一个点的坐标,用于追踪路径
int bfs(){
memset(d,-1,sizeof d);// 初始化所有点的最短距离为-1
d[1][1] = 0; //首先将起点(1, 1)的最短距离设置为0,表示从起点到起点的距离为0,
q.push({1,1}); //把起点放入队列中。
int dx[4] ={0,0,-1,1},dy[4] = {1,-1,0,0};//上下左右
while(q.size()){//当队列中还有坐标
auto t = q.front(); // 获取队列前端元素,即当前处理的点
q.pop(); // 弹出当前处理的点
for(int i = 0;i < 4;i++){
int x = t.first + dx[i],y = t.second + dy[i];//遍历四个方向
//如果这个相邻点有效(在网格范围内)、未被访问过(d[x][y] == -1)、且没有障碍物(g[x][y] == 0),
if(x >= 1 && y >= 1 && x <= n && y <= m && d[x][y] == - 1 && g[x][y] == 0){//记住是y <= m不是y <= n
d[x][y] = d[t.first][t.second] + 1; //更新这个点的最短距离为d[t.first][t.second] + 1
prevNode[x][y] = t; // 记录前驱点,是由t来到(x,y)的。
q.push({x,y}); //将其坐标加入队列中。
}
}
}
//循环结束后,d[n][m]中存储的就是从起点(1, 1)到终点(n, m)的最短距离。
//如果终点不可达,结果将保持为初始化时的-1。
return d[n][m];
}
void print_path() {
if (d[n][m] == -1) {
cout << “终点不可达。” << endl;
return;
}
vector[HTML_REMOVED]> path;
// 从终点开始逆向追踪到起点
//这里为什么逆向追踪呢?因为我们储存的是前驱节点,我们只知道到达了终点(n,m),所以要先找(n,m)的前驱节点a,
//再找a的前驱节点b,直到到达(1,1)
//这个过程就像是沿着一条线索,从故事的结局逐步回溯到开头一样。
//make_pair(1, 1) 创建了一个包含两个整数的 pair
for (pair<int, int> at = {n, m}; at != make_pair(1, 1); at = prevNode[at.first][at.second]) {
path.push_back(at);
}
path.push_back({1, 1}); // 加入起点
reverse(path.begin(), path.end()); // 将路径逆序,因为我们是逆向追踪的
for (auto p : path) {
cout << "(" << p.first << ", " << p.second << ")" << " -> ";
}
cout << "End" << endl;
}
int main() {
cin >> n >> m;
for(int i = 1;i <= n;i){
for(int j = 1;j <= m;j){
cin >> g[i][j];
}
}
cout << bfs() << endl; // 执行BFS搜索并输出从起点到终点的最短距离
print_path(); // 打印找到的路径
return 0;