目录
牛客_AB20走迷宫_BFS
描述：
给定一个n×m的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(xs,ys)(xs,ys)到(xt,yt)(xt,yt)最少的移动次数。若不能到达，输出−1。
输入描述：
第一行输入两个整数n,mn,m (1≤n,m≤10001≤n,m≤1000)，表示网格大小。
第二行输入四个整数xs,ys,xt,ytxs,ys,xt,yt (1≤xs,xt≤n1≤xs,xt≤n, 1≤ys,yt≤m1≤ys,yt≤m)，表示起点和终点的坐标。
接下来的n行，每行输入一个长度为m的字符串。其中，第i行第j个字符表示第i行第j列的格子上的障碍物情况，若字符为'*'，则格子上有障碍物，若字符为'.'，则格子上没有障碍物。保证起点不存在障碍物。
输出描述：
输出一行一个整数，表示从(xs,ys)(xs,ys)到(xt,yt)(xt,yt)最少的移动次数。
题目解析
-
广度优先遍历，是一种层次遍历。它从起点开始，从上往下、从左到右进行遍历。这种层次遍历，可以确保起点到终点的路径是 最短的。最坏情况下，也就是将所有的节点遍历一次，才能找到终点。但是呢，广度优先遍历不太适用于找路径的条数，归根结底，还是因为一般的层次遍历，节点只知道自己当前所在的层次，并不知道自己是由哪一个节点过来的。
- 判断是两个坐标是否相同，相同返回零。
- bfs广度优先搜索，用while循环将新创建的steps[][]进行层次遍历迭代。
- 判断目标坐标内容是否发生改变，如果没有，那么无法bsf到该目标坐标，返回-1。
C++代码
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int n = 0, m = 0;
int x1, y1, x2, y2;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool vis[1007][1007];
void bfs(vector<vector<char>>& vv, vector<vector<int>>& cnt)
{
queue<pair<int, int>> q;
q.push({x1, y1});
vis[x1][y1] = true;
while(q.size())
{
auto[a, b] = q.front();
q.pop();
if(a == x2 && b == y2)
return;
for(int i = 0; i < 4; ++i)
{
int x = dx[i] + a, y = dy[i] + b;
// cout << x << " " << y << endl;
if(x <= n && x > 0 && y <= m && y > 0
&& !vis[x][y] && vv[x][y] == '.')
{
q.push({x, y});
vis[x][y] = true;
cnt[x][y] = cnt[a][b] + 1;
// cout << x << " " << y << endl;
// cout << cnt << endl;
}
}
}
}
signed main()
{
cin >> n >> m;
cin >> x1 >> y1 >> x2 >> y2;
vector<vector<char>> vv(n + 1, vector<char>(m + 1));
vector<vector<int>> cnt(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> vv[i][j];
}
}
if(vv[x1][y1] == '*' || vv[x2][y2] == '*')
{
cout << -1 << endl;
return 0;
}
bfs(vv, cnt);
// for(int i = 1; i <= n; ++i)
// {
// for(int j = 1; j <= m; ++j)
// {
// cout << cnt[i][j] << " ";
// }
// cout << endl;
// }
if(cnt[x2][y2] == 0)
cout << -1 << endl;
else
cout << cnt[x2][y2] << endl;
return 0;
}Java代码
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
public static int N = 1010;
public static int[] dx = {0, 0, 1, -1};
public static int[] dy = {-1, 1, 0, 0};
public static int n, m, x1, y1, x2, y2;
public static char[][] arr = new char[N][N];
public static int[][] dist = new int[N][N]; // 标记当前位置有没有搜索过，以及⾛到该位置时候的最短步数
public static int bfs()
{
if(arr[x2][y2] == '*')
return -1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
dist[i][j] = -1; // 表明刚开始每个位置都没有搜索过
}
}
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x1, y1});
dist[x1][y1] = 0;
while(!q.isEmpty())
{
int[] t = q.poll();
int a = t[0], b = t[1];
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if(x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == '.' && dist[x][y] == -1)
{
q.add(new int[]{x, y});
dist[x][y] = dist[a][b] + 1;
if(x == x2 && y == y2)
{
return dist[x][y];
}
}
}
}
return -1;
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
n = in.nextInt(); m = in.nextInt();
x1 = in.nextInt(); y1 = in.nextInt();
x2 = in.nextInt(); y2 = in.nextInt();
for(int i = 1; i <= n; i++)
{
String tmp = in.next();
for(int j = 1; j <= m; j++)
{
arr[i][j] = tmp.charAt(j - 1);
}
}
System.out.println(bfs());
}
}