Submission #420225


Source Code Expand

import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
	
	public static final int[] vs = {0, 1, 0, -1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int H = sc.nextInt();
		final int W = sc.nextInt();
		
		int sx = -1, sy = -1, gx = -1, gy = -1;
		boolean[][] is_wall = new boolean[H][W];
		
		for(int i = 0; i < H; i++){
			char[] inputs = sc.next().toCharArray();
			
			for(int j = 0; j < inputs.length; j++){
				if(inputs[j] == '#'){
					is_wall[i][j] = true;
				}else if(inputs[j] == 's'){
					sx = j;
					sy = i;
				}else if(inputs[j] == 'g'){
					gx = j;
					gy = i;
				}
			}
		}
		
		LinkedList<Integer> x_queue = new LinkedList<Integer>();
		LinkedList<Integer> y_queue = new LinkedList<Integer>();
		int[][] depth = new int[H][W];
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				depth[i][j] = Integer.MAX_VALUE;
			}
		}
		depth[sy][sx] = 0;
		x_queue.add(sx);
		y_queue.add(sy);
		
		while(!x_queue.isEmpty()){
			final int x = x_queue.poll();
			final int y = y_queue.poll();
			
			for(int index = 0; index < vs.length; index++){
				final int nx = x + vs[index];
				final int ny = y + vs[(index + 1) % vs.length];
				
				if(nx < 0 || nx >= W || ny < 0 || ny >= H){
					continue;
				}else if(is_wall[ny][nx]){
					continue;
				}
				
				final int next_cost = depth[y][x] + 1;
				if(next_cost >= depth[ny][nx]){
					continue;
				}
				depth[ny][nx] = next_cost;
				x_queue.add(nx);
				y_queue.add(ny);
			}
		}
		
		
		System.out.println(depth[gy][gx] == Integer.MAX_VALUE ? "No" : "Yes");
		
		sc.close();
	}
}

Submission Info

Submission Time
Task A - 深さ優先探索
User mondatto
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1707 Byte
Status AC
Exec Time 663 ms
Memory 37904 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 448 ms 24064 KB
00_min_02.txt AC 378 ms 23948 KB
00_min_03.txt AC 374 ms 23956 KB
00_min_04.txt AC 374 ms 23944 KB
00_min_05.txt AC 386 ms 23932 KB
00_min_06.txt AC 384 ms 23952 KB
00_min_07.txt AC 385 ms 23948 KB
00_min_08.txt AC 384 ms 23964 KB
00_sample_01.txt AC 375 ms 23924 KB
00_sample_02.txt AC 412 ms 23972 KB
00_sample_03.txt AC 395 ms 23864 KB
00_sample_04.txt AC 426 ms 23840 KB
00_sample_05.txt AC 404 ms 23948 KB
01_rnd_00.txt AC 512 ms 29988 KB
01_rnd_01.txt AC 596 ms 36308 KB
01_rnd_02.txt AC 590 ms 36184 KB
01_rnd_03.txt AC 596 ms 36336 KB
01_rnd_04.txt AC 619 ms 36972 KB
01_rnd_05.txt AC 503 ms 29556 KB
01_rnd_06.txt AC 636 ms 37904 KB
01_rnd_07.txt AC 585 ms 36240 KB
01_rnd_08.txt AC 565 ms 29920 KB
01_rnd_09.txt AC 503 ms 29556 KB
01_rnd_10.txt AC 596 ms 35340 KB
01_rnd_11.txt AC 493 ms 29456 KB
01_rnd_12.txt AC 597 ms 36364 KB
01_rnd_13.txt AC 585 ms 36252 KB
01_rnd_14.txt AC 498 ms 29472 KB
01_rnd_15.txt AC 663 ms 35204 KB
01_rnd_16.txt AC 519 ms 29776 KB
01_rnd_17.txt AC 588 ms 35408 KB
01_rnd_18.txt AC 521 ms 29956 KB
01_rnd_19.txt AC 596 ms 35940 KB
02_rndhard_00.txt AC 505 ms 30004 KB
02_rndhard_01.txt AC 501 ms 29772 KB
02_rndhard_02.txt AC 549 ms 31364 KB
02_rndhard_03.txt AC 544 ms 31600 KB
02_rndhard_04.txt AC 494 ms 29512 KB
02_rndhard_05.txt AC 497 ms 29764 KB
02_rndhard_06.txt AC 499 ms 29700 KB
02_rndhard_07.txt AC 500 ms 29668 KB
02_rndhard_08.txt AC 535 ms 29976 KB
02_rndhard_09.txt AC 540 ms 30340 KB
02_rndhard_10.txt AC 534 ms 30500 KB
02_rndhard_11.txt AC 522 ms 30644 KB
02_rndhard_12.txt AC 530 ms 30012 KB
02_rndhard_13.txt AC 512 ms 29968 KB
02_rndhard_14.txt AC 553 ms 30492 KB
02_rndhard_15.txt AC 545 ms 30084 KB
02_rndhard_16.txt AC 493 ms 29760 KB
02_rndhard_17.txt AC 521 ms 29776 KB
02_rndhard_18.txt AC 501 ms 29584 KB
02_rndhard_19.txt AC 502 ms 30024 KB
02_rndhard_20.txt AC 507 ms 29992 KB
02_rndhard_21.txt AC 513 ms 29828 KB
02_rndhard_22.txt AC 535 ms 30016 KB
02_rndhard_23.txt AC 517 ms 30076 KB
02_rndhard_24.txt AC 511 ms 29660 KB
02_rndhard_25.txt AC 512 ms 29532 KB
02_rndhard_26.txt AC 534 ms 30232 KB
02_rndhard_27.txt AC 492 ms 29696 KB
02_rndhard_28.txt AC 511 ms 29836 KB
02_rndhard_29.txt AC 511 ms 29868 KB
02_rndhard_30.txt AC 503 ms 29624 KB
02_rndhard_31.txt AC 508 ms 29692 KB
02_rndhard_32.txt AC 543 ms 30220 KB
02_rndhard_33.txt AC 519 ms 30220 KB
02_rndhard_34.txt AC 514 ms 29788 KB
02_rndhard_35.txt AC 498 ms 29704 KB
02_rndhard_36.txt AC 507 ms 29572 KB
02_rndhard_37.txt AC 509 ms 29648 KB
02_rndhard_38.txt AC 524 ms 29944 KB
02_rndhard_39.txt AC 518 ms 30160 KB
03_rndhardsmall_00.txt AC 365 ms 23968 KB
03_rndhardsmall_01.txt AC 364 ms 23952 KB
03_rndhardsmall_02.txt AC 375 ms 23916 KB
03_rndhardsmall_03.txt AC 394 ms 23932 KB
03_rndhardsmall_04.txt AC 404 ms 23920 KB
03_rndhardsmall_05.txt AC 371 ms 23864 KB
03_rndhardsmall_06.txt AC 381 ms 23952 KB
03_rndhardsmall_07.txt AC 377 ms 23944 KB
03_rndhardsmall_08.txt AC 370 ms 23952 KB
03_rndhardsmall_09.txt AC 373 ms 23904 KB