[PS][완전탐색][BFS]/[BOJ][2206][벽 부수고 이동하기]

boj2206.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int n=0, m=0, dist=1;
int map[1000][1000];
bool visited[1000][1000][2];
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
int cx, cy, cb;
queue<pair<pair<int, int>, int> > q;

void bfs(int x, int y){
	int size = 0;
	q.push(make_pair(make_pair(x,y),0));
	visited[x][y][0] = true;
	while(!q.empty()){
		size = q.size();
		while(size--){
			cx = q.front().first.first;
			cy = q.front().first.second;
			cb = q.front().second;
			if(cx == n-1 && cy == m-1){
				cout<< dist;
				return;
			}
			q.pop();
			for(int k=0; k<4; k++){
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if(nx<0 || nx>=n) continue;
				if(ny<0 || ny>=m) continue;
				if(map[nx][ny] == 0 && !visited[nx][ny][cb]){
					visited[nx][ny][cb] = true;
					q.push(make_pair(make_pair(nx,ny),cb));
				}else{
					if(cb == 0 && !visited[nx][ny][1]){
						visited[nx][ny][1] = true;
						q.push(make_pair(make_pair(nx,ny),1));
					}
				}
			}
		}
		dist++;
	}
	cout<< -1;
	return;
}

int main (void){
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin>> n>> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%1d", &map[i][j]);
		}
	}
	bfs(0,0);
	return 0;
}