結果

問題 No.8063 幅優先探索
ユーザー joybeeee
提出日時 2020-05-14 15:08:04
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,089 ms / 2,000 ms
コード長 1,633 bytes
コンパイル時間 2,300 ms
コンパイル使用メモリ 78,696 KB
実行使用メモリ 122,324 KB
最終ジャッジ日時 2024-09-15 07:20:53
合計ジャッジ時間 6,320 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main {

  private static int ROWS = 1001;

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int r = sc.nextInt();
      int c = sc.nextInt();
      int sy = sc.nextInt() - 1, sx = sc.nextInt() - 1;
      int gy = sc.nextInt() - 1, gx = sc.nextInt() - 1;
      char[][] grid = new char[r][c];
      for(int i = 0; i < r; i++)
        grid[i] = sc.next().toCharArray();

      int steps = 0;
      Queue<Integer> queue = new LinkedList<>();
      queue.offer(sx * ROWS + sy);
      Set<Integer> visited = new HashSet<>();
      visited.add(sx * ROWS + sy);

      int[] rows = new int[]{-1, 1, 0, 0};
      int[] cols = new int[]{0, 0, -1, 1};
      while(!queue.isEmpty()) {
        int size = queue.size();
        for(int i = 0; i < size; i++) {
          int pos = queue.poll();
          int col = pos / ROWS;
          int row = pos % ROWS;
          if(col == gx && row == gy) {
              System.out.println(steps);
              return;
          }
          for(int j = 0; j < rows.length; j++) {
            int nextRow = row + rows[j];
            int nextCol = col + cols[j];
            if(!isValid(grid, visited, nextRow, nextCol)) continue;
            queue.offer(nextCol * ROWS + nextRow);
            visited.add(nextCol * ROWS + nextRow);
          }
        }
        steps++;
      }
  }

  private static boolean isValid(char[][] grid, Set<Integer> visited, int row, int col) {
    if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited.contains(col * ROWS + row))
      return false;
    return true;
  }
}
0