AtCoder Typical Contest 001

Submission #5349487

Source codeソースコード

import java.io.IOException;
import java.io.InputStream;
import java.util.*;


public class Main {
	
    public static void main(String[] args) {
    	FastScanner sc = new FastScanner();
    	
    	int h = sc.nextInt();
    	int w = sc.nextInt();
    	
    	int si = -1;
    	int sj = -1;
    	int gi = -1;
    	int gj = -1;
    	
    	IntGrid g = new IntGrid(h,w);
    	
    	for(int i=0;i<h;i++){
    		char[] c = sc.next().toCharArray();
    		
    		for(int j=0;j<w;j++){
    			
    			switch(c[j]){
    			case 's':
    				g.grid[i][j] = 2;
    				si = i;
    				sj = j;
    				break;
    			case 'g':
    				g.grid[i][j] = 2;
    				gi = i;
    				gj = j;
    				break;
    			case '#':
    				g.grid[i][j] = 1;
    				break;
    			case '.':
    				g.grid[i][j] = 2;
    				break;
    			default:	
    			}
    			
    		}
    	}
    	
    	boolean[][] visited = new boolean[h][w];
    	ArrayDeque<Pair> q = new ArrayDeque<>();
    	boolean can = false;
    	
    	visited[si][sj] = true;
    	q.add(new Pair(si,sj));
    	
    	loop:while(!q.isEmpty()){
    		Pair now = q.pollFirst();
    		
    		for(Pair p: g.nextSet(now.a, now.b)){
    			if(p.a == gi && p.b == gj){
    				can = true;
    				break loop;
    			}
    			else if(!visited[p.a][p.b] && g.grid[p.a][p.b] == 2){
    				q.offerFirst(new Pair(p.a,p.b));
    				visited[p.a][p.b] = true;
    			}
    		}
    		
    	}
    	
    	if(can){
    		System.out.println("Yes");
    	}
    	else{
    		System.out.println("No");
    	}
    }
    
}

class IntGrid {
	int[][] grid;
	
	public IntGrid(int h, int w){
		this.grid = new int[h][w];
	}
	
	//(n,m)に隣接するグリッドを全て返す
	java.util.LinkedList<Pair> nextSet(int n, int m){
		java.util.LinkedList<Pair> list = new java.util.LinkedList<>();
		
		if(n>0){
			list.add(new Pair(n-1,m));
		}
		
		if(n<this.grid.length-1){
			list.add(new Pair(n+1,m));
		}
		
		if(m>0){
			list.add(new Pair(n,m-1));
		}
		
		if(m<this.grid[0].length-1){
			list.add(new Pair(n,m+1));
		}
		
		return list;
	}
	
}

class Pair implements Comparable<Pair>{
	int a,b;
	
	public Pair(int a, int b){
		this.a = a;
		this.b = b;
	}
	
	@Override
	public boolean equals(Object o){
		if(o instanceof Pair){
			Pair p = (Pair) o;
			return a == p.a && b == p.b;
		}
		return super.equals(o);
	}
	
	@Override
	public int compareTo(Pair o){
		if(a!=o.a){
			return Integer.compare(a,o.a);
		}
		return Integer.compare(b, o.b);
	}
	
	@Override
	public int hashCode(){
		return (a<<16)+b;
	}
	
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Submission

Task問題 A - 深さ優先探索
User nameユーザ名 warachia
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 4817 Byte
File nameファイル名
Exec time実行時間 275 ms
Memory usageメモリ使用量 63268 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 71 ms 18900 KB
00_min_02.txt AC 71 ms 20308 KB
00_min_03.txt AC 70 ms 20820 KB
00_min_04.txt AC 71 ms 20820 KB
00_min_05.txt AC 71 ms 19028 KB
00_min_06.txt AC 69 ms 18388 KB
00_min_07.txt AC 72 ms 24916 KB
00_min_08.txt AC 71 ms 22868 KB
00_sample_01.txt AC 71 ms 21328 KB
00_sample_02.txt AC 70 ms 19540 KB
00_sample_03.txt AC 70 ms 21460 KB
00_sample_04.txt AC 73 ms 20820 KB
00_sample_05.txt AC 69 ms 20820 KB
01_rnd_00.txt AC 106 ms 25684 KB
01_rnd_01.txt AC 275 ms 63268 KB
01_rnd_02.txt AC 161 ms 40472 KB
01_rnd_03.txt AC 135 ms 31652 KB
01_rnd_04.txt AC 216 ms 47008 KB
01_rnd_05.txt AC 104 ms 25812 KB
01_rnd_06.txt AC 113 ms 26324 KB
01_rnd_07.txt AC 249 ms 45968 KB
01_rnd_08.txt AC 112 ms 25812 KB
01_rnd_09.txt AC 110 ms 25428 KB
01_rnd_10.txt AC 210 ms 43820 KB
01_rnd_11.txt AC 111 ms 23252 KB
01_rnd_12.txt AC 161 ms 39320 KB
01_rnd_13.txt AC 186 ms 44948 KB
01_rnd_14.txt AC 111 ms 25940 KB
01_rnd_15.txt AC 145 ms 35104 KB
01_rnd_16.txt AC 145 ms 24916 KB
01_rnd_17.txt AC 225 ms 44268 KB
01_rnd_18.txt AC 108 ms 25812 KB
01_rnd_19.txt AC 234 ms 45424 KB
02_rndhard_00.txt AC 119 ms 26068 KB
02_rndhard_01.txt AC 104 ms 24916 KB
02_rndhard_02.txt AC 139 ms 34344 KB
02_rndhard_03.txt AC 133 ms 32724 KB
02_rndhard_04.txt AC 114 ms 25556 KB
02_rndhard_05.txt AC 121 ms 27644 KB
02_rndhard_06.txt AC 122 ms 24660 KB
02_rndhard_07.txt AC 114 ms 25556 KB
02_rndhard_08.txt AC 119 ms 23764 KB
02_rndhard_09.txt AC 111 ms 22996 KB
02_rndhard_10.txt AC 125 ms 25300 KB
02_rndhard_11.txt AC 121 ms 23636 KB
02_rndhard_12.txt AC 112 ms 24532 KB
02_rndhard_13.txt AC 129 ms 25428 KB
02_rndhard_14.txt AC 119 ms 23764 KB
02_rndhard_15.txt AC 118 ms 26068 KB
02_rndhard_16.txt AC 109 ms 26836 KB
02_rndhard_17.txt AC 123 ms 25940 KB
02_rndhard_18.txt AC 109 ms 25172 KB
02_rndhard_19.txt AC 108 ms 26188 KB
02_rndhard_20.txt AC 105 ms 23892 KB
02_rndhard_21.txt AC 109 ms 26704 KB
02_rndhard_22.txt AC 108 ms 26324 KB
02_rndhard_23.txt AC 114 ms 25684 KB
02_rndhard_24.txt AC 116 ms 25044 KB
02_rndhard_25.txt AC 122 ms 25428 KB
02_rndhard_26.txt AC 120 ms 24916 KB
02_rndhard_27.txt AC 109 ms 25812 KB
02_rndhard_28.txt AC 119 ms 25812 KB
02_rndhard_29.txt AC 117 ms 26576 KB
02_rndhard_30.txt AC 122 ms 25812 KB
02_rndhard_31.txt AC 111 ms 23380 KB
02_rndhard_32.txt AC 118 ms 26196 KB
02_rndhard_33.txt AC 115 ms 23764 KB
02_rndhard_34.txt AC 110 ms 24916 KB
02_rndhard_35.txt AC 113 ms 24148 KB
02_rndhard_36.txt AC 117 ms 24660 KB
02_rndhard_37.txt AC 116 ms 26068 KB
02_rndhard_38.txt AC 108 ms 26580 KB
02_rndhard_39.txt AC 107 ms 27044 KB
03_rndhardsmall_00.txt AC 70 ms 21460 KB
03_rndhardsmall_01.txt AC 71 ms 20820 KB
03_rndhardsmall_02.txt AC 79 ms 19540 KB
03_rndhardsmall_03.txt AC 71 ms 22868 KB
03_rndhardsmall_04.txt AC 70 ms 18644 KB
03_rndhardsmall_05.txt AC 70 ms 21332 KB
03_rndhardsmall_06.txt AC 71 ms 20052 KB
03_rndhardsmall_07.txt AC 70 ms 21332 KB
03_rndhardsmall_08.txt AC 71 ms 21204 KB
03_rndhardsmall_09.txt AC 70 ms 20436 KB