結果

問題 No.340 雪の足跡
ユーザー uafr_csuafr_cs
提出日時 2016-02-08 21:33:41
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
37,312 KB
testcase_01 AC 56 ms
37,572 KB
testcase_02 AC 54 ms
37,368 KB
testcase_03 AC 52 ms
36,932 KB
testcase_04 AC 54 ms
37,268 KB
testcase_05 AC 54 ms
37,284 KB
testcase_06 AC 54 ms
37,220 KB
testcase_07 AC 52 ms
37,168 KB
testcase_08 AC 53 ms
37,064 KB
testcase_09 AC 53 ms
36,932 KB
testcase_10 AC 53 ms
37,408 KB
testcase_11 AC 158 ms
43,160 KB
testcase_12 AC 134 ms
43,348 KB
testcase_13 AC 185 ms
45,460 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.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