結果
| 問題 |
No.340 雪の足跡
|
| ユーザー |
 Kilisame
|
| 提出日時 | 2016-05-24 15:28:17 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,661 bytes |
| コンパイル時間 | 2,136 ms |
| コンパイル使用メモリ | 79,340 KB |
| 実行使用メモリ | 150,212 KB |
| 最終ジャッジ日時 | 2024-10-07 05:51:56 |
| 合計ジャッジ時間 | 12,696 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 24 TLE * 1 -- * 7 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
public class Main {
private int w;
private int h;
/* [0]そこから上へ移動できるか。[1]そこから右へ移動できるか。[2]すでに踏破チェック済みか */
private boolean[][] blocks;
private static final String ODEKAKEDEKINAI = "Odekakedekinai..";
private void initField(int w, int h) {
this.w = w;
this.h = h;
blocks = new boolean[w * h][3];
}
private void execute() {
if (w * h - 1 == 0) {
System.out.println(0);
System.exit(0);
}
/* block[0]を起点として、移動開始 */
Set<Integer> next = new HashSet<Integer>();
next.add(0);
int stepCount = 0;
while (true) {
next = step(next);
stepCount++;
if (next.isEmpty()) {
System.out.println(ODEKAKEDEKINAI);
break;
}
if (next.contains(w * h - 1)) {
System.out.println(stepCount);
break;
}
}
}
private Set<Integer> step(Set<Integer> beforeBlocks) {
Set<Integer> nextBlocks = new HashSet<Integer>();
for (int number : beforeBlocks) {
/* 現在numberに踏破済みのフラグ(blocks[number][2]=true)を立てる */
blocks[number][2] = true;
/* 上移動チェック */
if (blocks[number][0] && !blocks[number + w][2]) {
nextBlocks.add(number + w);
}
/* 下移動チェック */
if (number > w && blocks[number - w][0] && !blocks[number - w][2]) {
nextBlocks.add(number - w);
}
/* 左移動チェック */
if (number % w != 0 && blocks[number - 1][1] && !blocks[number - 1][2]) {
nextBlocks.add(number - 1);
}
/* 右移動チェック */
if (blocks[number][1] && !blocks[number + 1][2]) {
nextBlocks.add(number + 1);
}
}
return nextBlocks;
}
private void footprint(int min, int max) {
if (min / w == max / w) {
/* 横の移動 = minとmaxをwで割ったときの値が等しい */
for (int i = min; i < max; i++) {
/* 左側(数が小さいほうのblock)から右へと移動できるので、blocks[i][1]をtrue */
blocks[i][1] = true;
}
} else {
/* 縦の移動 */
for (int i = min; i < max; i += w) {
/* 下側(数が小さいほうのblock)から上へと移動できるので、blocks[i][0]をtrue */
blocks[i][0] = true;
}
}
}
public static void main(String[] args) {
FastScanner cin = new FastScanner();
Main snow = new Main();
int w = Integer.parseInt(cin.next());
int h = Integer.parseInt(cin.next());
snow.initField(w, h);
Map<Integer, Set<Integer>> checkedMap = new HashMap<Integer, Set<Integer>>();
int limit = Integer.parseInt(cin.next());
for (int i = 0; i < limit; i++) {
int index = Integer.parseInt(cin.next());
int[] currentArray = new int[2];
currentArray[1] = Integer.parseInt(cin.next());
for (int j = 0; j < index; j++) {
currentArray[j % 2] = Integer.parseInt(cin.next());
int min = Math.min(currentArray[0], currentArray[1]);
int max = Math.max(currentArray[0], currentArray[1]);
if (!checkedMap.containsKey(min)) {
Set<Integer> set = new HashSet<Integer>();
set.add(max);
checkedMap.put(min, set);
} else {
Set<Integer> set = checkedMap.get(min);
if (set.contains(max)) {
continue;
}
set.add(max);
}
snow.footprint(min, max);
}
}
snow.execute();
}
}
/**
* http://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4 よりFastScannerをお借りして実装。
*/
class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
}