結果

問題 No.8063 幅優先探索
ユーザー joybeeeejoybeeee
提出日時 2020-05-14 15:08:04
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 130 ms
41,120 KB
testcase_01 AC 134 ms
41,076 KB
testcase_02 AC 132 ms
41,096 KB
testcase_03 AC 130 ms
41,068 KB
testcase_04 AC 129 ms
41,084 KB
testcase_05 AC 128 ms
41,400 KB
testcase_06 AC 814 ms
89,924 KB
testcase_07 AC 1,089 ms
122,324 KB
testcase_08 AC 128 ms
41,276 KB
testcase_09 AC 126 ms
41,504 KB
testcase_10 AC 137 ms
41,320 KB
権限があれば一括ダウンロードができます

ソースコード

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