結果

問題 No.340 雪の足跡
ユーザー uafr_cs
提出日時 2016-02-08 21:33:41
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,020 bytes
コンパイル時間 2,366 ms
コンパイル使用メモリ 79,788 KB
実行使用メモリ 45,460 KB
最終ジャッジ日時 2024-09-21 21:50:16
合計ジャッジ時間 6,898 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 9 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		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..");
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}
0