結果
問題 | No.8063 幅優先探索 |
ユーザー | joybeeee |
提出日時 | 2020-05-14 15:04:01 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,658 bytes |
コンパイル時間 | 2,334 ms |
コンパイル使用メモリ | 78,020 KB |
実行使用メモリ | 122,136 KB |
最終ジャッジ日時 | 2024-09-15 07:15:51 |
合計ジャッジ時間 | 6,302 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
41,292 KB |
testcase_01 | AC | 131 ms
41,276 KB |
testcase_02 | AC | 130 ms
41,416 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 1,211 ms
122,136 KB |
testcase_08 | AC | 130 ms
41,344 KB |
testcase_09 | AC | 123 ms
40,216 KB |
testcase_10 | AC | 131 ms
41,460 KB |
ソースコード
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; } }