Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement