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

boj16933.cpp

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

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

void bfs(int x, int y){
	int size = 0;
	q.push(make_pair(make_pair(x,y),make_pair(0,false)));
	visited[x][y][0][false] = true;
	while(!q.empty()){
		size = q.size();
		while(size--){
			cx = q.front().first.first;
			cy = q.front().first.second;
			wall = q.front().second.first;
			day = q.front().second.second;
			if(cx == n-1 && cy == m-1){
				cout<< dist;
				return;
			}
			q.pop();
			for(int i=0; i<4; i++){
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if(nx<0 || nx>=n) continue;
				if(ny<0 || ny>=m) continue;
				if(map[nx][ny] == 0 && !visited[nx][ny][wall][!day]){
					visited[nx][ny][wall][!day] = true;
					q.push(make_pair(make_pair(nx,ny),make_pair(wall,!day)));
				}else{
					if( !day && wall < k && !visited[nx][ny][wall+1][!day]){
						//다음이 벽 && 낮 &&  더 부술 수 있음 && 방문가능
						visited[nx][ny][wall+1][!day] = true;
						q.push(make_pair(make_pair(nx,ny),make_pair(wall+1, !day)));
					}else if( day && wall < k && !visited[cx][cy][wall][!day]){
						//다음이 벽 && 밤 &&  더 부술 수 있음 && 방문가능
						visited[cx][cy][wall][!day] = true;
						q.push(make_pair(make_pair(cx,cy),make_pair(wall,!day)));
					}
				}
			}
		}
		dist++;
	}
	cout<< -1;
	return;
}

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