Skip to content

Instantly share code, notes, and snippets.

@Ryunosuke0203 Ryunosuke0203/DFS.java
Last active May 10, 2019

Embed
What would you like to do?
DFS - ATC001-A
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");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.