結果
問題 | No.157 2つの空洞 |
ユーザー | jp_ste |
提出日時 | 2015-03-17 11:19:06 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 2,769 bytes |
コンパイル時間 | 2,169 ms |
コンパイル使用メモリ | 74,624 KB |
実行使用メモリ | 58,268 KB |
最終ジャッジ日時 | 2023-09-11 08:30:48 |
合計ジャッジ時間 | 5,787 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 127 ms
55,652 KB |
testcase_01 | AC | 127 ms
55,604 KB |
testcase_02 | AC | 126 ms
55,560 KB |
testcase_03 | AC | 127 ms
56,028 KB |
testcase_04 | AC | 127 ms
55,916 KB |
testcase_05 | AC | 126 ms
56,080 KB |
testcase_06 | AC | 129 ms
55,828 KB |
testcase_07 | AC | 128 ms
55,700 KB |
testcase_08 | AC | 125 ms
56,072 KB |
testcase_09 | AC | 125 ms
55,832 KB |
testcase_10 | AC | 126 ms
55,696 KB |
testcase_11 | AC | 128 ms
55,592 KB |
testcase_12 | AC | 137 ms
57,756 KB |
testcase_13 | AC | 132 ms
58,064 KB |
testcase_14 | AC | 127 ms
55,808 KB |
testcase_15 | AC | 133 ms
57,752 KB |
testcase_16 | AC | 133 ms
57,676 KB |
testcase_17 | AC | 129 ms
55,860 KB |
testcase_18 | AC | 142 ms
58,268 KB |
testcase_19 | AC | 138 ms
57,672 KB |
ソースコード
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int W, H; static char C[][]; static int DP[][]; static int mAns = Integer.MAX_VALUE; public static void main(String[] args) { readMap(); boolean find = false; for(int i=0; i<H; i++) { for(int j=0; j<W; j++) { if(C[i][j] == '.') { replaceCavity(j, i, '+'); find=true; break; } } if(find) break; } for(int i=0; i<H; i++) { for(int j=0; j<W; j++) { if(C[i][j] == '.') { solve(j, i); } } } System.out.println(mAns-1); } static void solve(int startX, int startY) { Queue<Node> q = new LinkedList<Node>(); Node start = new Node(startX, startY, 0, C); q.add(start); while(!q.isEmpty()) { Node node = q.poll(); if(DP[node.mY][node.mX] <= node.mStep) continue; DP[node.mY][node.mX] = node.mStep; if(mAns <= node.mStep) continue; if(node.mX == 0 || node.mX == W-1) continue; if(node.mY == 0 || node.mY == H-1) continue; if(node.mMap[node.mY][node.mX] == '+') { mAns = Math.min(mAns, node.mStep); continue; } node.mMap[node.mY][node.mX] = '.'; int nextStep = node.mStep+1; int nextX, nextY; char nextMap[][] = node.mMap; //上 nextX = node.mX; nextY = node.mY-1; if(node.mMap[nextY][nextX] != '.') { Node next = new Node(nextX, nextY, nextStep, nextMap); q.add(next); } //右 nextX = node.mX+1; nextY = node.mY; if(node.mMap[nextY][nextX] != '.') { Node next = new Node(nextX, nextY, nextStep, nextMap); q.add(next); } //下 nextX = node.mX; nextY = node.mY+1; if(node.mMap[nextY][nextX] != '.') { Node next = new Node(nextX, nextY, nextStep, nextMap); q.add(next); } //左 nextX = node.mX-1; nextY = node.mY; if(node.mMap[nextY][nextX] != '.') { Node next = new Node(nextX, nextY, nextStep, nextMap); q.add(next); } } } static void readMap() { Scanner sc = new Scanner(System.in); W = sc.nextInt(); H = sc.nextInt(); C = new char[H][W]; DP = new int[H][W]; for(int i=0; i<H; i++) { String line = sc.next(); for(int j=0; j<W; j++) { C[i][j] = line.charAt(j); DP[i][j] = Integer.MAX_VALUE; } } } static void replaceCavity(int j, int i, char v) { if(C[i][j] != '.') return; C[i][j] = v; replaceCavity(j+1, i , v); replaceCavity(j , i+1, v); replaceCavity(j-1, i , v); replaceCavity(j , i-1, v); } } class Node { int mX, mY, mStep; char mMap[][]; Node(int x, int y, int step, char[][] map) { mX = x; mY = y; mStep = step; mMap = new char[Main.H][Main.W]; for(int i=0; i<Main.H; i++) { mMap[i] = map[i].clone(); } } }