結果

問題 No.3063 幅優先探索
ユーザー joybeeeejoybeeee
提出日時 2020-05-14 15:08:04
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,182 ms / 2,000 ms
コード長 1,633 bytes
コンパイル時間 3,516 ms
コンパイル使用メモリ 75,036 KB
実行使用メモリ 133,584 KB
最終ジャッジ日時 2023-10-13 10:15:33
合計ジャッジ時間 7,680 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
55,688 KB
testcase_01 AC 126 ms
55,712 KB
testcase_02 AC 126 ms
56,044 KB
testcase_03 AC 124 ms
56,088 KB
testcase_04 AC 131 ms
55,860 KB
testcase_05 AC 128 ms
55,352 KB
testcase_06 AC 859 ms
100,424 KB
testcase_07 AC 1,182 ms
133,584 KB
testcase_08 AC 126 ms
56,068 KB
testcase_09 AC 124 ms
54,372 KB
testcase_10 AC 127 ms
56,592 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