[BOJ] 2206. 벽 부수고 이동하기

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

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int M=sc.nextInt();
		int map[][]=new int [N][M];
		int dx[]= {-1,1,0,0};
		int dy[]= {0,0,-1,1};
		int d[][][]=new int [N][M][2];
		
		for (int i = 0; i < N; i++) {
			char s[]=new char[M];
			s=sc.next().toCharArray();
			for(int j=0;j<M;j++) {
				map[i][j]=s[j]-'0';
			}
		}
		
		Queue<Point> q=new LinkedList<>();
		q.add(new Point(0,0,0));
		d[0][0][0]=1;
		while(!q.isEmpty()) {
			Point c=q.poll();
			for(int i=0;i<4;i++) {
				int nx=c.x+dx[i];
				int ny=c.y+dy[i];
				if(!(0<=nx && nx<N && 0<=ny && ny<M)) continue;
				if(d[nx][ny][c.f]==0 && map[nx][ny]==0) {
					q.add(new Point(nx,ny,c.f));
					d[nx][ny][c.f]=d[c.x][c.y][c.f]+1;
				}
				if(c.f==0 && d[nx][ny][c.f]==0 && map[nx][ny]==1) {
					q.add(new Point(nx,ny,1));
					d[nx][ny][1]=d[c.x][c.y][0]+1;
				}
			}
		}
		int ans;
		if(d[N-1][M-1][0]!=0 && d[N-1][M-1][1]!=0) {
			ans=Math.min(d[N-1][M-1][0],d[N-1][M-1][1]);
		}else if(d[N-1][M-1][0]!=0) {
			ans=d[N-1][M-1][0];
		}else if(d[N-1][M-1][1]!=0) {
			ans=d[N-1][M-1][1];
		}else {
			ans=-1;
		}
		System.out.println(ans);
		
	}
	
	static class Point {
		int x,y,f;
		Point(int x,int y,int f){
			this.x=x;
			this.y=y;
			this.f=f;
		}
	}
}