目录
牛客_AB20走迷宫_BFS
题目解析
C++代码
Java代码
牛客_AB20走迷宫_BFS
走迷宫_牛客题霸_牛客网 (nowcoder.com)
描述：
给定一个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;elsecout << 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());}
}
