0.题目
1.题解
1.1 BFS搜索
思路
这里为何使用BFS搜索呢?由于我们求得是最短路径,BFS广度优先多种情况齐头并进,必然有一种情况最先到达终止条件,这时我们直接终止搜索即可,不像DFS深度搜索一种情况不对还要进行回溯,造成大量重复计算.
这里使用BFS搜索,我们依旧要考虑终止条件,边界条件,以及构建BFS搜索.
1.终止条件(check函数):到达终点(x2,y2); 如果BFS搜索结束(while循环结束)还没有找到,就输出-1
2.边界条件(pd函数): 不可超出边界,不可重复走,不可走有障碍的路径
3.BFS搜索:
3.1 初始化
3.2 外层while循环
3.3 内层使用简单图论+for训话,表示向四周移动; 使用队列实现BFS搜索
3.4 使用vis数组记录到达当前位置步数. 1.不会重复,pd函数中有专门判断 2.一定是最小,由于是BFS搜索,肯定是先记录到较小步数,之后其他较大步数不会记录
注意:
1.这里我使用x1,y1,x2,y2作为初始坐标,发生了报错:mathcalls.h 中已经定义了 double y1(double),后改为使用pair对直接表示
2.不要使用map关键字作为标识符!!!
代码
#include<bits/stdc++.h>
using namespace std;
int n, m;
int Map[101][101];
int vis[101][101] = {0};
pair<int, int> Start, End;int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};// 路径检测
bool pd(int x, int y) {// 超出边界if(x < 1 || x > n || y < 1 || y > m) {return false;}// 已经走过了if(vis[x][y] >= 1) {return false;}// 不是路径不能走if(Map[x][y] != 1) {return false;}return true;
}// 终点检测
bool check(int x, int y) {if(x == End.first && y == End.second) {cout << vis[x][y];return true;}return false;
}void BFS() {// 初始化queue<pair<int, int>> q;q.push(make_pair(Start.first, Start.second));
// vis[x1][y1] = 1;// BFS总循环while(!q.empty()) {pair<int, int> tempNode = q.front();int x = tempNode.first;int y = tempNode.second;q.pop();// 进行BFS扩展for(int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 通过路径检测if(pd(newX, newY)) {// 更新vis值 vis[newX][newY] = vis[x][y] + 1;// 进行结果检测if(check(newX, newY)) {exit(0);}// 不是最终点,更新队列q.push(make_pair(newX, newY)); }}}cout << -1;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cin >> Map[i][j];}}cin >> Start.first >> Start.second >> End.first >> End.second;BFS();
}
