結果

問題 No.340 雪の足跡
ユーザー uafr_cs
提出日時 2016-02-08 21:31:28
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 9 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

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