結果
問題 | No.2897 2集合間距離 |
ユーザー |
![]() |
提出日時 | 2024-09-20 22:54:03 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 629 ms / 3,500 ms |
コード長 | 1,526 bytes |
コンパイル時間 | 2,732 ms |
コンパイル使用メモリ | 78,464 KB |
実行使用メモリ | 68,924 KB |
最終ジャッジ日時 | 2024-09-20 22:54:14 |
合計ジャッジ時間 | 10,832 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int mx = 1000; int[][] d = new int[mx][mx]; Queue<Integer> que = new ArrayDeque<>(); for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); int x = Integer.parseInt(sa[0]); int y = Integer.parseInt(sa[1]); d[x][y] = 1; que.add(x * mx + y); } boolean[][] g = new boolean[mx][mx]; int m = Integer.parseInt(br.readLine()); for (int i = 0; i < m; i++) { String[] sa = br.readLine().split(" "); int z = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); g[z][w] = true; } br.close(); int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; while (!que.isEmpty()) { int cur = que.poll(); int cx = cur / mx; int cy = cur % mx; if (g[cx][cy]) { System.out.println(d[cx][cy] - 1); return; } for (int i = 0; i < 4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx < 0 || mx <= nx || ny < 0 || mx <= ny) { // g[nx][ny] == '#' みたいな条件もあれば continue; } int next = nx * mx + ny; if (d[nx][ny] == 0) { que.add(next); d[nx][ny] = d[cx][cy] + 1; // if (g[nx][ny]) { // System.out.println(d[nx][ny] - 1); // return; // } } } } } }