結果
| 問題 | No.340 雪の足跡 |
| ユーザー |
 Kilisame
|
| 提出日時 | 2016-06-08 11:24:53 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,687 bytes |
| コンパイル時間 | 2,897 ms |
| コンパイル使用メモリ | 80,648 KB |
| 実行使用メモリ | 51,068 KB |
| 最終ジャッジ日時 | 2024-10-09 02:55:16 |
| 合計ジャッジ時間 | 19,323 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 27 TLE * 5 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.Comparator;import java.util.HashSet;import java.util.Iterator;import java.util.NoSuchElementException;import java.util.Scanner;import java.util.Set;import java.util.TreeSet;public class Main {private int w;private int h;private Set<int[]>[] wSetArray;private Set<int[]>[] hSetArray;private boolean[] moved;private static final String ODEKAKEDEKINAI = "Odekakedekinai..";private static IntArrayComparator comparator;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);snow.footPrint(cin);snow.execute();}private void initField(int w, int h) {this.w = w;this.h = h;comparator = new IntArrayComparator();wSetArray = new Set[w];for (int i = 0; i < w; i++) {wSetArray[i] = new TreeSet<int[]>(comparator);}hSetArray = new Set[h];for (int i = 0; i < h; i++) {hSetArray[i] = new TreeSet<int[]>(comparator);}moved = new boolean[w * h];}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を踏破済みSetに入れる。falseが返った場合は既に踏破していたところなのでSkip */moved[number] = true;/* 上移動チェック */if (number < w * (h - 1) && !moved[number + w] && canMove(new int[] {number, number + w})) {nextBlocks.add(number + w);}/* 下移動チェック */if (number > w && !moved[number - w] && canMove(new int[] {number - w, number})) {nextBlocks.add(number - w);}/* 左移動チェック */if (number % w != 0 && !moved[number - 1] && canMove(new int[] {number - 1, number})) {nextBlocks.add(number - 1);}/* 右移動チェック */if (number % w != w - 1 && !moved[number + 1] && canMove(new int[] {number, number + 1})) {nextBlocks.add(number + 1);}}return nextBlocks;}private void footPrint(FastScanner cin) {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[] oneStep = new int[2];oneStep[0] = Math.min(currentArray[0], currentArray[1]);oneStep[1] = Math.max(currentArray[0], currentArray[1]);recordStep(oneStep);}}}private void recordStep(int[] oneStep) {Set<int[]> targetSet;if (oneStep[0] / w == oneStep[1] / w) {/* 横の移動 = minとmaxをwで割ったときの値が等しい */int hindex = oneStep[0] / w;targetSet = hSetArray[hindex];} else {/* 縦の移動 */int windex = oneStep[0] % w;targetSet = wSetArray[windex];}if (targetSet.contains(oneStep)) {return;}Iterator<int[]> iterator = targetSet.iterator();while (iterator.hasNext()) {int[] current = iterator.next();if (oneStep[1] < current[0]) {/* 範囲重複なし。これ以降のチェックは不要。そこまでの足跡を記録 */break;}if (oneStep[0] > current[1]) {/* 範囲重複なし。次の足跡との比較へ移る */continue;}if (oneStep[0] >= current[0] && oneStep[1] <= current[1]) {/* 完全に吸収。記録不要。 */return;}/* 範囲重複のため書き換え。現在値を置き換える */oneStep[0] = Math.min(oneStep[0], current[0]);oneStep[1] = Math.max(oneStep[1], current[1]);iterator.remove();}targetSet.add(oneStep);}private boolean canMove(int[] oneStep) {Set<int[]> targetSet;if (oneStep[0] / w == oneStep[1] / w) {/* 横の移動 = minとmaxをwで割ったときの値が等しい */int hindex = oneStep[0] / w;targetSet = hSetArray[hindex];} else {/* 縦の移動 */int windex = oneStep[0] % w;targetSet = wSetArray[windex];}Iterator<int[]> iterator = targetSet.iterator();while (iterator.hasNext()) {int[] current = iterator.next();if (oneStep[1] < current[0]) {break;}if (oneStep[0] > current[1]) {continue;}if (oneStep[0] >= current[0] && oneStep[1] <= current[1]) {return true;}}return false;}class IntArrayComparator implements Comparator<int[]> {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] == o2[0] ? o1[1] == o2[1] ? 0 : o1[1] - o2[1] : o1[0] - o2[0];}}}/*** 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++];elsereturn -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());}}