DFS - ATC001-A

DFS.java

import java.util.*;
import java.awt.Point;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
　　　　// 右左上下を見るための配列生成
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        int h = sc.nextInt();
        int w = sc.nextInt();
        char map[][] = new char[h][w];
		
	//その場所に行ったことがあるかどうかをメモする配列
        boolean memo[][] = new boolean[h][w];
        int sx = 0;
        int sy = 0;
        int gx = 0;
        int gy = 0;

        for(int i=0; i<h; i++){
            map[i] = sc.next().toCharArray();
            for(int j=0; j<w; j++){
		    
		// startとgoalの座標を保存する。
                if(map[i][j]=='s'){
                    sx = j;
                    sy = i;
                }else if(map[i][j]=='g'){
                    gx = j;
                    gy = i;
                }
            }
        }
		
	// スタック生成
        Deque<Point> stack = new ArrayDeque<Point>();
		
	// Pointオブジェクトを生成しスタックにいれる。
	// オブジェクトを生成することでxとy両方の情報を保持することができる。
        stack.addFirst(new Point(sx,sy));
		
	// startは行くことを許されているのでTrueとしてメモする。
        memo[sy][sx] = true;
	
	// スタックが空になるまで繰り返す。
        while(!stack.isEmpty()){
		
　　　　　　　//スタックに入れた要素を取り出すし、pに入れる。
            Point p = stack.removeFirst();
　　　　　　　
	    // 4方向を見てみる。(実際にトレースしてみるとわかります。)
            for(int i=0; i<4; i++){
                int x = p.x + dx[i];
                int y = p.y + dy[i];
		 
		// 4方向を見て、マップ外だったらエラーが出るのでケアする。
                if(x>=0 && x<w && y>=0 && y<h){
			
		    // 壁ではない。かつ今の場所のメモがfalseのとき
                    if(map[y][x]!='#' && !memo[y][x]){
　　　　　　　　　　　　　// 今の場所をスタックに入れる。
                        stack.addFirst(new Point(x,y));
　　　　　　　　　　　　　// 今の場所は行けるのでTrueとメモする。
                        memo[y][x] = true;
                    }
                }
            }
        }
　　　　// goalのメモをみてTrue(行ける)ならYes‼
        if(memo[gy][gx]){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}