[백준 : 2206] 벽 부수고 이동하기 -BFS

public class Main {

	public static int N;
	public static int M;
	public static int map[][];
	public static boolean visit[][][];
	public static int dp[][][];
	public static int dx[] = { 1, 0, -1, 0 };
	public static int dy[] = { 0, 1, 0, -1 };
	public static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visit = new boolean[N][M][2];
		dp = new int[N][M][2];

		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = line.charAt(j) - '0';
				dp[i][j][0] = Integer.MAX_VALUE;
				dp[i][j][1] = Integer.MAX_VALUE;
			}
		}

		bfs();

		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
	}

	public static int bfs() {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0, 0, 0, 1));

		int nx, ny;
		while (!q.isEmpty()) {
			Node n = q.poll();

			if (n.x == N - 1 && n.y == M - 1) {
				min = Math.min(min, n.depth);
				continue;
			}

			for (int d = 0; d < 4; d++) {
				nx = n.x + dx[d];
				ny = n.y + dy[d];

				if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny][n.broke]) {
					continue;
				}

				if (map[nx][ny] == 0) {
					visit[nx][ny][n.broke] = true;
					q.offer(new Node(nx, ny, n.broke, n.depth + 1));
				} else {
					if (n.broke == 0) {
						visit[nx][ny][1] = true;
						q.offer(new Node(nx, ny, 1, n.depth + 1));
					} else {
						continue;
					}
				}
			}
		}

		return 0;
	}

	static class Node {
		int x;
		int y;
		int broke;
		int depth;

		public Node(int x, int y, int broke, int depth) {
			super();
			this.x = x;
			this.y = y;
			this.broke = broke;
			this.depth = depth;
		}
	}
}