AtCoder Typical Contest 001

Submission #420184

Source codeソースコード

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni(), m = ni();
		char[][] map = nm(n,m);
		int sr = -1, sc = -1;
		int gr = -1, gc = -1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(map[i][j] == 's'){
					sr = i; sc = j;
					map[i][j] = '.';
				}
				if(map[i][j] == 'g'){
					gr = i; gc = j;
					map[i][j] = '.';
				}
			}
		}
		
		Queue<int[]> q = new ArrayDeque<int[]>();
		q.add(new int[]{sr, sc});
		int[] dr = { 1, 0, -1, 0 };
		int[] dc = { 0, 1, 0, -1 };
		while(!q.isEmpty()){
			int[] cur = q.poll();
			int r = cur[0], c = cur[1];
			for(int k = 0;k < 4;k++){
				int nr = r + dr[k];
				int nc = c + dc[k];
				if(nr >= 0 && nr < n && nc >= 0 && nc < m && map[nr][nc] == '.'){
					map[nr][nc] = '#';
					q.add(new int[]{nr, nc});
				}
			}
		}
		out.println(map[gr][gc] == '#' ? "Yes" : "No");
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission

Task問題 A - 深さ優先探索
User nameユーザ名 うい
Created time投稿日時
Language言語 Java (OpenJDK 1.7.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 4310 Byte
File nameファイル名
Exec time実行時間 623 ms
Memory usageメモリ使用量 30812 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,00_sample_05.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_min_01.txt AC 623 ms 22896 KB
00_min_02.txt AC 322 ms 22800 KB
00_min_03.txt AC 320 ms 22796 KB
00_min_04.txt AC 321 ms 22796 KB
00_min_05.txt AC 315 ms 22712 KB
00_min_06.txt AC 406 ms 22796 KB
00_min_07.txt AC 315 ms 22716 KB
00_min_08.txt AC 319 ms 22792 KB
00_sample_01.txt AC 323 ms 22796 KB
00_sample_02.txt AC 315 ms 22740 KB
00_sample_03.txt AC 328 ms 22684 KB
00_sample_04.txt AC 314 ms 22796 KB
00_sample_05.txt AC 313 ms 22796 KB
01_rnd_00.txt AC 347 ms 24788 KB
01_rnd_01.txt AC 388 ms 30352 KB
01_rnd_02.txt AC 386 ms 28980 KB
01_rnd_03.txt AC 388 ms 30720 KB
01_rnd_04.txt AC 394 ms 30200 KB
01_rnd_05.txt AC 349 ms 24884 KB
01_rnd_06.txt AC 387 ms 28752 KB
01_rnd_07.txt AC 383 ms 29060 KB
01_rnd_08.txt AC 347 ms 24736 KB
01_rnd_09.txt AC 348 ms 24748 KB
01_rnd_10.txt AC 375 ms 27380 KB
01_rnd_11.txt AC 352 ms 24584 KB
01_rnd_12.txt AC 394 ms 29684 KB
01_rnd_13.txt AC 389 ms 29724 KB
01_rnd_14.txt AC 349 ms 24588 KB
01_rnd_15.txt AC 383 ms 28356 KB
01_rnd_16.txt AC 348 ms 24712 KB
01_rnd_17.txt AC 394 ms 28084 KB
01_rnd_18.txt AC 352 ms 24664 KB
01_rnd_19.txt AC 392 ms 30812 KB
02_rndhard_00.txt AC 356 ms 24628 KB
02_rndhard_01.txt AC 354 ms 24636 KB
02_rndhard_02.txt AC 364 ms 25552 KB
02_rndhard_03.txt AC 360 ms 25400 KB
02_rndhard_04.txt AC 341 ms 24580 KB
02_rndhard_05.txt AC 339 ms 24624 KB
02_rndhard_06.txt AC 347 ms 24784 KB
02_rndhard_07.txt AC 346 ms 24672 KB
02_rndhard_08.txt AC 365 ms 25024 KB
02_rndhard_09.txt AC 363 ms 24892 KB
02_rndhard_10.txt AC 363 ms 25008 KB
02_rndhard_11.txt AC 364 ms 25016 KB
02_rndhard_12.txt AC 361 ms 24868 KB
02_rndhard_13.txt AC 361 ms 24848 KB
02_rndhard_14.txt AC 365 ms 25028 KB
02_rndhard_15.txt AC 360 ms 24968 KB
02_rndhard_16.txt AC 345 ms 24688 KB
02_rndhard_17.txt AC 347 ms 24840 KB
02_rndhard_18.txt AC 341 ms 24608 KB
02_rndhard_19.txt AC 348 ms 24872 KB
02_rndhard_20.txt AC 346 ms 24616 KB
02_rndhard_21.txt AC 348 ms 24716 KB
02_rndhard_22.txt AC 365 ms 24888 KB
02_rndhard_23.txt AC 348 ms 24856 KB
02_rndhard_24.txt AC 340 ms 24612 KB
02_rndhard_25.txt AC 346 ms 24804 KB
02_rndhard_26.txt AC 341 ms 24632 KB
02_rndhard_27.txt AC 342 ms 24908 KB
02_rndhard_28.txt AC 344 ms 24736 KB
02_rndhard_29.txt AC 361 ms 24656 KB
02_rndhard_30.txt AC 354 ms 24660 KB
02_rndhard_31.txt AC 361 ms 24744 KB
02_rndhard_32.txt AC 366 ms 24736 KB
02_rndhard_33.txt AC 354 ms 24860 KB
02_rndhard_34.txt AC 354 ms 24580 KB
02_rndhard_35.txt AC 358 ms 24652 KB
02_rndhard_36.txt AC 356 ms 24620 KB
02_rndhard_37.txt AC 350 ms 24596 KB
02_rndhard_38.txt AC 348 ms 24620 KB
02_rndhard_39.txt AC 355 ms 24792 KB
03_rndhardsmall_00.txt AC 318 ms 22708 KB
03_rndhardsmall_01.txt AC 321 ms 22768 KB
03_rndhardsmall_02.txt AC 313 ms 22788 KB
03_rndhardsmall_03.txt AC 320 ms 22768 KB
03_rndhardsmall_04.txt AC 322 ms 22800 KB
03_rndhardsmall_05.txt AC 334 ms 22732 KB
03_rndhardsmall_06.txt AC 324 ms 22768 KB
03_rndhardsmall_07.txt AC 321 ms 22796 KB
03_rndhardsmall_08.txt AC 325 ms 22800 KB
03_rndhardsmall_09.txt AC 328 ms 22780 KB