[BOJ] 16954. 움직이는 미로 탈출

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

public class Main {
	static int ans;
	static int dx[]= {-1,1,0,0,-1,1,-1,1,0};
	static int dy[]= {0,0,-1,1,-1,-1,1,1,0};
	static char map[][];
	static Queue<Point> q;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		map=new char [8][8];
		for(int i=0;i<8;i++) {
			map[i]=sc.next().toCharArray();
		}

		q=new LinkedList<Point>();
		q.add(new Point(7,0,0));
		bfs();
		System.out.println(ans);
	}
	
	public static void bfs() {
		while(!q.isEmpty()) {
			Point cur=q.poll();
			int x=cur.x;
			int y=cur.y;
			int t=cur.t;
			if((x==0 && y==7)||ans==1||t==16) {
				ans=1;
				break;
			}
			for (int i = 0; i < 9; i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(0<=nx && nx<8 && 0<=ny && ny<8) {
					if(nx-t-1>=0 && map[nx-t-1][ny]=='#') continue;
					if(nx-t>=0 && map[nx-t][ny]=='#') continue;
					q.add(new Point(nx,ny,t+1));
				}
			}
		}
	}
	
	static class Point{
		int x, y, t;
		Point(int x,int y,int t){
			this.x=x;
			this.y=y;
			this.t=t;
		}
	}
}

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

public class Main {
	public static void print(char map[][]) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	static int ans;
	static int dx[]= {-1,1,0,0,-1,1,-1,1,0};
	static int dy[]= {0,0,-1,1,-1,-1,1,1,0};
	static char map[][];
	static Queue<Point> q;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		map=new char [8][8];
		for(int i=0;i<8;i++) {
			map[i]=sc.next().toCharArray();
		}
		
		q=new LinkedList<Point>();
		q.add(new Point(7,0,0));
		dfs(7,0,0);
		System.out.println(ans);
	}
	
	public static void dfs(int x,int y,int t) {
		if(ans==1 || t==16) {
			return;
		}
		if(x==0 && y==7) {
			ans=1;
			return;
		}
		for (int i = 0; i < 9; i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(0<=nx && nx<8 && 0<=ny && ny<8) {
				if(nx-t-1>=0 && map[nx-t-1][ny]=='#') continue;
				if(nx-t>=0 && map[nx-t][ny]=='#') continue;
				dfs(nx,ny,t+1);
			}
		}
	}
	
	static class Point{
		int x, y, t;
		Point(int x,int y,int t){
			this.x=x;
			this.y=y;
			this.t=t;
		}
	}
}