2178号:迷宮ナビゲーション


質問する



2178号:迷宮ナビゲーション

に近づく

  • 1(移動可能なセル)に沿って座標の端点に移動します.
  • これは
  • bfsを用いた典型的な距離測定問題である.
  • マイコード

    import java.io.*;
    import java.util.*;
    
    public class Main {
        static int[][] grid = new int[101][101];
        static int[][] distance = new int[101][101];
        static Queue<Node> queue = new LinkedList<>();
        static int[] dx = {0, 0, -1, 1}; // 상,하,좌,우
        static int[] dy = {1, -1, 0, 0};
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st;
        public static void main(String[] args) throws IOException {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            for (int i = 0; i < N; i++) {
                String str = br.readLine(); // String 한 줄을 입력받는다.(공백x)
                for (int j = 0; j < M; j++) {
                    grid[i][j] = str.charAt(j)-'0'; // 문자->int (0 또는 1)
                }
            }
            for (int[] d : distance) {
                Arrays.fill(d, -1); // 거리 계산을 위한 초기화
            }
            queue.add(new Node(0, 0));
            distance[0][0] = 1;
            while (!queue.isEmpty()) {
                Node now = queue.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int x = now.getX() + dx[dir];
                    int y = now.getY() + dy[dir];
                    if (x < 0 || x >= N || y < 0 || y >= M) continue;
                    if (grid[x][y] != 1 || distance[x][y] >= 0) continue;
                    distance[x][y] = distance[now.getX()][now.getY()] + 1;
                    queue.add(new Node(x, y));
                }
            }
            System.out.println(distance[N-1][M-1]);
        }
    
        static class Node {
            private final int x;
            private final int y;
    
            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
    
            public int getX() {
                return x;
            }
    
            public int getY() {
                return y;
            }
        }
    }
  • bfsを知っていれば、すぐに解ける典型的なタイプです.