結果

問題 No.340 雪の足跡
ユーザー uafr_csuafr_cs
提出日時 2016-02-08 21:31:28
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,053 bytes
コンパイル時間 2,629 ms
コンパイル使用メモリ 86,300 KB
実行使用メモリ 113,852 KB
最終ジャッジ日時 2024-09-21 21:50:09
合計ジャッジ時間 7,582 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
46,924 KB
testcase_01 AC 119 ms
41,760 KB
testcase_02 AC 122 ms
41,216 KB
testcase_03 AC 120 ms
41,176 KB
testcase_04 AC 120 ms
40,788 KB
testcase_05 AC 116 ms
41,204 KB
testcase_06 AC 121 ms
41,356 KB
testcase_07 AC 113 ms
41,164 KB
testcase_08 AC 126 ms
41,384 KB
testcase_09 AC 108 ms
40,208 KB
testcase_10 AC 126 ms
41,480 KB
testcase_11 AC 271 ms
48,768 KB
testcase_12 AC 239 ms
47,852 KB
testcase_13 AC 267 ms
49,260 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int W = sc.nextInt();
		final int H = sc.nextInt();
		final int N = sc.nextInt();
		
		ArrayList<HashSet<Integer>> adj = new ArrayList<HashSet<Integer>>();
		for(int i = 0; i < W * H; i++){
			adj.add(new HashSet<Integer>());
		}
		
		for(int i = 0; i < N; i++){
			final int M = sc.nextInt();
			
			int prev = sc.nextInt();
			int prev_y = prev / W;
			int prev_x = prev % W;
			
			for(int j = 0; j < M; j++){
				final int cur = sc.nextInt();
				final int cur_y = cur / W;
				final int cur_x = cur % W;
				
				if(prev_y == cur_y){
					final int y = cur_y;
					final int min_x = Math.min(prev_x, cur_x);
					final int max_x = Math.max(prev_x, cur_x);
					
					for(int p_x = min_x, c_x = min_x + 1; c_x <= max_x; p_x = c_x, c_x++){
						adj.get(y * W + p_x).add(y * W + c_x);
						adj.get(y * W + c_x).add(y * W + p_x);
					}
				}else{
					final int x = cur_x;
					final int min_y = Math.min(prev_y, cur_y);
					final int max_y = Math.max(prev_y, cur_y);
					
					for(int p_y = min_y, c_y = min_y + 1; c_y <= max_y; p_y = c_y, c_y++){
						adj.get(c_y * W + x).add(p_y * W + x);
						adj.get(p_y * W + x).add(c_y * W + x);
					}
				}
				
				prev = cur;
				prev_x = cur_x;
				prev_y = cur_y;
			}
		}
		
		LinkedList<Integer> queue = new LinkedList<Integer>();
		int[] costs = new int[H * W];
		Arrays.fill(costs, Integer.MAX_VALUE);
		
		queue.add(0);
		costs[0] = 0;
		
		while(!queue.isEmpty()){
			final int pos = queue.poll();
			
			if(pos == (W * H - 1)){
				System.out.println(costs[pos]);
				return;
			}
			
			for(final int next : adj.get(pos)){
				final int next_cost = costs[pos] + 1;
				
				if(costs[next] > next_cost){
					costs[next] = next_cost;
					queue.add(next);
				}
			}
		}
		
		System.out.println("Odekakedekinai..");
	}

}
0