結果

問題 No.3063 幅優先探索
ユーザー joybeeeejoybeeee
提出日時 2020-05-14 15:04:01
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 1,658 bytes
コンパイル時間 2,029 ms
コンパイル使用メモリ 74,912 KB
実行使用メモリ 133,664 KB
最終ジャッジ日時 2023-10-13 10:10:42
合計ジャッジ時間 6,441 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
56,020 KB
testcase_01 AC 122 ms
55,756 KB
testcase_02 AC 122 ms
55,912 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 1,133 ms
133,664 KB
testcase_08 AC 122 ms
55,768 KB
testcase_09 AC 122 ms
56,176 KB
testcase_10 AC 123 ms
55,656 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) || grid[row][col] == '#')
      return false;
    return true;
  }
}
0