Submission #145134

---

Source Code Expand

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		new Main().run();
	}

	int H, W;
	void run()
	{
		Scanner cin = new Scanner(System.in);
		H = cin.nextInt();
		W = cin.nextInt();
		String[] board = new String[H];
		for(int i=0;i<H;i++){
			board[i] = cin.next();
		}

		//sの場所を探す
		int fx = -1;
		int fy = -1;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(board[i].charAt(j) == 's'){
					fy = i;
					fx = j;
				}
			}
		}

		//初期状態の挿入
		Queue<Integer> nowq = new LinkedList<Integer>();
		nowq.add(encode(fy, fx));

		//移動先の列挙
		int[] vy = new int[]{1,0,-1,0};
		int[] vx = new int[]{0,1,0,-1};

		//到達したかどうかのチェック用
		boolean[][] check = new boolean[H][W];
		check[fy][fx] = true;

		//幅優先探索を三回繰り返す
		for(int i = 0; i < 3; i++){

			//破壊した壁を入れるキューを用意する
			Queue<Integer> nextq = new LinkedList<Integer>();

			//幅優先探索
			while(!nowq.isEmpty()){
				//現在位置を取ってくる
				int now = nowq.poll();
				int y = now / 1000;
				int x = now % 1000;

				//4方向に移動できるので、それぞれの移動先を調べる
				for(int j=0;j<4;j++){
					int ny = y + vy[j];
					int nx = x + vx[j];

					//範囲外だったらcontinue
					if(!ok(ny,nx)) continue;
					//既に調べてあるマスだったらcontinue
					if(check[ny][nx]) continue;

					//調査済みフラグを立てる
					check[ny][nx] = true;

					//ゴールなら終了
					if(board[ny].charAt(nx) == 'g'){
						System.out.println("YES");
						return;
					}
					//壁なら壁用キューに入れる
					else if(board[ny].charAt(nx) == '#'){
						nextq.add(encode(ny,nx));
					}
					//それ以外なら通常のキューに入れる
					else{
						nowq.add(encode(ny,nx));
					}
				}

			}
			nowq = nextq;
		}
		System.out.println("NO");
		return;
	}

	int encode(int y, int x){
		return y * 1000 + x;
	}

	boolean ok(int y, int x){
		return y >= 0 && x >= 0 && y < H && x < W;
	}
}

Submission Info

Judge Result