벽부수고 이동하기3

www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#include<cstring>
#include<string>

using namespace std;
int n, m;
int map[1001][1001];
bool check[1001][1001][11]; //check에다가 총움직인횟수를 더해주는 대신 true false 로 체크 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };


typedef struct  {

	int x;
	int y;
	int	br; //부신 횟수
	int nd; // 낮:0, 밤:1 
	int dist; // 총 움직인 횟수

}info;



int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int wall;
	cin >> n;
	cin >> m;
	cin >> wall;

	memset(check, 0, sizeof(check));

	string s;

	for (int i = 0; i < n; i++) {
		cin >> s; //입력값이 붙어있어서 string 형으로 받는다.
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j] - '0';  //각각을 숫자의 형태로 만들어준다.
		}
	}
	queue<info> q;

	check[0][0][0]=true; 

	q.push({0,0,0,0,1}); //시작
	int count = -1;

	while (!q.empty()) {
		
		int x = q.front().x;
		int y = q.front().y;
		int br = q.front().br;
		int nd = q.front().nd;
		int dist = q.front().dist;

		q.pop();

		if (x == n - 1 && y == m - 1) {
			count = dist;
			break;
		}


		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) {
				
			  if (map[nx][ny] == 1) { //벽이 있는 경우
				
                //벽을 뚫을 수 있는 횟수보다 적게 뚫었고 , 체크배열에서 false이면
					if ((br < wall) && (check[nx][ny][br + 1]==false)) { 
						if (nd == 0) { //낮이라면 큐에 넣어준다, 단 밤으로 바꾸어준 후에
							check[nx][ny][br + 1] = true;  
							q.push({nx,ny,br + 1 ,1,dist+1 });
						}
						else {
							//밤이라면 낮으로 바꾸어서 다시 넣어준다. 
							q.push({ x,y,br,0,dist+1});
							
						}
					}
				
				}
				else { //벽이 없는 경우 
					
					if (check[nx][ny][br] == false) {
						check[nx][ny][br] = true;
						
						if (nd == 0) { //낮일때 -> 밤으로 바꾸어서 큐에 넣어줌
							q.push({nx,ny,br,1,dist+1});
						}
						else { //밤일때 -> 낮으로 바꾸어서 큐에 넣어줌
							q.push({ nx,ny,br,0,dist+1 });
						}
					}
				}

			}
		}
	
	}

	cout << count ;
	return 0;

}