[백준/C++] 14442 벽 부수고 이동하기 2

생각지 못한 오류 2

- 미로가 0 하나인 경우 -1이 출력되서 틀려버림

- 부순 벽 개수에 따른 visit를 따로 나눴는데 최대 11개의 경우의 수인데 10개라고 했음. 이런 경우 계속 23%에서 틀렸다고 함. visit[11][1000][1000]으로 바꿔서 해결

/*
백준 14442 벽 부수고 이동하기2

문제
- N*M의 미로, 최단 경로 이동(시작하는 칸, 끝나는 칸 포함)
- K개의 벽을 부수고 이동 가능
- 항상 1,1에서 출발 N,M에 도착
- 최단 거리 출력, 못가면 -1출력

풀이
- visit를 하나만 두기엔 경우의 수가 너무 많다!
- BFS로 풀되, visit를 남은 부수기 갯수(?)에 따라서 경우를 나누면 될듯!
- 겉에 장벽 둘건지?? -> 벽을 부술 수 있으므로 그냥 일일이 확인해도 될듯..

까먹어버린 경우의 수
- 1 1 K 인경우 -1이 나왔음
*/

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int visit[11][1000][1000] = {0,};
int maze[1000][1000];
int N,M,K;
int px[4] = {0,0,1,-1};
int py[4] = {1,-1,0,0};

void findWay(){
	queue<pair<int, pair<int,int>>> q;
	int x,y,tempx,tempy, k;

	q.push({K,{0,0}});
	visit[K][0][0] = 1;

	while(!q.empty()){
		x = q.front().second.first;
		y = q.front().second.second;
		k = q.front().first;
		q.pop();

		for(int i=0;i<4;i++){
			tempx = x + px[i];
			tempy = y + py[i];
			if(tempx<0||tempy<0||tempx>=N||tempy>=M) continue;
			
			if(tempx == N-1 && tempy == M-1){
				cout << visit[k][x][y] + 1;
				return;
			}

			if(maze[tempx][tempy] == 0 && visit[k][tempx][tempy] == 0){
				q.push({k, {tempx,tempy}});
				visit[k][tempx][tempy] = visit[k][x][y]+1;
			}else if(k-1>=0 && maze[tempx][tempy] == 1 && visit[k-1][tempx][tempy] == 0){
				q.push({k-1, {tempx, tempy}});
				visit[k-1][tempx][tempy] = visit[k][x][y]+1;
			}
		}
	}

	cout << -1;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string temp;

	cin >> N >> M >> K;
	for(int i=0;i<N;i++){
		cin >> temp;
		for(int j=0;j<M;j++){
			maze[i][j] = (int)(temp[j]-'0');
		}
	}

	if(N==1&&M==1){
		cout << 1;
		return 0;
	}

	findWay();
}