백준 14923 : 미로 탈출 문제풀이코드 C++

https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

 

문제 설명

https://dingcoding.tistory.com/95

백준 2206번: 벽 부수고 이동하기 문제풀이 및 반례 모음

백준 2206번 벽부수고 이동하기 문제와 똑같은 문제다.

 

벽을 부순 상태와 부수지 않은 상태를 나누어서 생각해야 한다.

 

설명은 위 링크를 참고

 

 

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, hx, hy, ex, ey, arr[1003][1003], vis[1003][1003][2];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};

void print() {
	for (int k = 1; k >= 0; k--) {
		if (k == 1) {
			cout << "벽 뚫기 전 \n";
		}
		else {
			cout << "벽 뚫은 후 \n";
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << vis[i][j][k] << ' ';
			}
			cout << '\n';
		}
	}
	cout << "\n";
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<Edge> Q;
	cin >> n >> m;
	cin >> hx >> hy;
	cin >> ex >> ey;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	vis[hx][hy][1] = 1;
	Q.push(Edge(hx, hy, 1));

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		/*print();*/

		if (x == ex && y == ey) {
			if (vis[x][y][1] == 0) {
				cout << vis[x][y][0]- 1;
			}
			else cout << vis[x][y][1] -1 ;
			return 0;
		}

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


			if (nx<=0 || nx>n || ny<=0 || ny>m) continue;

			// 벽 뚫을 수 있음
			if (op == 1) {
				if (arr[nx][ny] == 0 && vis[nx][ny][1]==0) {
					vis[nx][ny][1] = vis[x][y][1] + 1;
					//벽 방문 가능
					Q.push({ nx,ny,1 });
				}
				else if (arr[nx][ny] == 1) {
					vis[nx][ny][0] = vis[x][y][1] + 1;
					//이제 벽 방문 기회 없음 
					Q.push({ nx,ny,0 });
				}
			}
			else {//벽 뚫을 기회 없음 무조건 0으로만 다녀야함
				if (arr[nx][ny] == 0 && vis[nx][ny][0] == 0) {
					vis[nx][ny][0] = vis[x][y][0] + 1;
					Q.push({ nx,ny,0 });
				}
			}
		}



	}


	cout << -1;

	return 0;
}

백준 14923 미로탈출 문제