[백준 14923] 미로 탈출

분류 

bfs

요구사항

벽을 한번 부술 수 있다.

시작점에서 도착점까지 벽을 최대한 한번 부시고 도착할 수 있는 최소 이동거리 구하기

 

풀이

visit[][][2]로 3차원으로 선언한다

마지막 [2]는 벽을 부순 경우와 안 부순 경우를 나누는 것이다

어느 칸에 도달하든 그 도달하는 칸에는 앞의 (벽을 부쉈다, 안 부쉈다) 두가지 경우를 지속해서 가지고 간다

그리고 bfs로 탐색을 할 경우 최초 도달하였을 때가 최소 이동거리이다.

나머지는 일반적인 bfs처럼 풀이하면 AC 가능하다

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>

using namespace std;
struct go {
	int x;
	int y;
	int flag;
};
int n, m;
int sr, sc;
int er, ec;
int map[1010][1010];
int visit[1010][1010][2];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int solve(int r, int c) {
	queue<go> q;
	q.push({ r,c,0 });
	visit[r][c][0] = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
	//	cout << x << " " << y << endl;
		int flag = q.front().flag;
		if (x == (er - 1) && y == (ec - 1)) {
			return visit[x][y][flag];
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[nx][ny] == 0) {
				if (visit[nx][ny][flag] == 0) {
					visit[nx][ny][flag] = visit[x][y][flag] + 1;
					q.push({ nx,ny,flag });
				}
			}
			if (map[nx][ny] == 1) {
				if (flag == 0) {
					if (visit[nx][ny][flag] == 0) {
						visit[nx][ny][1] = visit[x][y][flag] + 1;
						q.push({ nx,ny,1 });
					}
				}
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d", &sr, &sc);
	scanf("%d%d", &er, &ec);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	int ans = solve(sr - 1, sc - 1);
	if (ans == 0) cout << -1 << endl;
	else cout << ans -1<< endl;
}