题解 | #走迷宫#

走迷宫

https://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64

//package 搜索.BFS.走迷宫;

import java.io.*;
import java.util.*;

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nums = in.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);

        nums = in.readLine().split(" ");
        int xb = Integer.parseInt(nums[0]) - 1; // 调整索引,以0开始
        int yb = Integer.parseInt(nums[1]) - 1;
        int xe = Integer.parseInt(nums[2]) - 1;
        int ye = Integer.parseInt(nums[3]) - 1;

        // 初始化迷宫和访问状态
        char[][] graph = new char[n][m];
        boolean[][] visited = new boolean[n][m];
        int[][] dist = new int[n][m];

        for (int i = 0; i < n; i++) {
            graph[i] = in.readLine().toCharArray();
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        in.close();

        // BFS
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(xb, yb));
        dist[xb][yb] = 0;

        int[] dx = {-1, 1, 0, 0}; // 方向数组
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            if (current.x == xe && current.y == ye) {
                out.write(dist[xe][ye] + "");
                out.close();
                return;
            }

		  //依次访问上下左右点
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                // 检查新坐标是否有效
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && graph[nx][ny] == '.' &&
                        !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[current.x][current.y] + 1;
                    queue.add(new Point(nx, ny));
                }
            }
        }

        out.write("-1"); // 如果没有路径
        out.close();
    }
}

全部评论

相关推荐

当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
牛客928043833号:在他心里你已经是他的员工了
点赞 评论 收藏
分享
若怜君欢:驾驶证去掉吧,PPT啥的也去掉,本硕课程去掉,导师和研究方向去掉;加入本硕排名(好才写);技能栏加入你会的那些控制算法和滤波算法,这个比你会啥啥啥软件更有用;获奖写上去,奖学金啊,有没有专利啊之类的 电机和硬件这一块,属于传统制造业,制造业实习并不多。多投一些攒攒经验,有实习最好,没有也不需要焦虑(制造业实习其实除了转正,没多大用处) 最后,划重点,等秋招开始后,把你所有社交软件都发一份简历上去,并经常更新,找人内推你!
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务