백준 2206 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;
int N,M;
int map[1001][1001];
int visited[1001][1001][2];
int res;
queue <pair<pair<int, int>, pair<int, int > > > q;
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };

void bfs() {

	while (!q.empty()) {
		int cx = q.front().first.first;
		int cy = q.front().first.second;
		int wall = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();
		if (cx == N - 1 && cy == M - 1) {
			res = cnt;
			break;
		}

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

			if (nx >= 0 && ny >= 0 && nx < N && ny < M && visited[nx][ny][0] == 0) {
				if (wall == 0) { //부신적 없다면 
					if (map[nx][ny] == 0 && visited[nx][ny][0] == 0) {
						q.push(make_pair(make_pair(nx, ny), make_pair(wall, cnt + 1)));
						visited[nx][ny][0] = 1;
					}
					else if (map[nx][ny] == 1 && visited[nx][ny][1] == 0) {
						q.push(make_pair(make_pair(nx, ny), make_pair(wall + 1 , cnt + 1)));
						visited[nx][ny][1] = 1;
					}
				}
				else if (wall == 1) { //부신적 있다면 
					if (map[nx][ny] == 0 && visited[nx][ny][1] == 0) {
						q.push(make_pair(make_pair(nx, ny), make_pair(wall, cnt + 1)));
						visited[nx][ny][1] = 1;
					}
				}
			}
		}

	}

	

}
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	res = -1;
	q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
	visited[0][0][0] = 1;
	bfs();
	
	printf("%d", res);
	
	return 0;

}