18933번 벽 부수고 이동하기3

2보다는 어렵고 4보다는 쉽다..
밤낮을 잘 구별하는게 포인트다.

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;
int map[1001][1001];
int ch[1001][1001][11][2];
int n, m, key;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct Loc {
	int x, y, z, night;
	Loc(int a, int b, int c, int d) {
		x = a;
		y = b;
		z = c;
		night = d;
	}
};
void init() {
	n = 0;
	m = 0;
	key = 0;
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	init();
	cin >> n >> m >> key;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	queue<Loc> Q;
	ch[1][1][0][0] = 1;
	Q.push(Loc(1, 1, 0,0));
	while (!Q.empty()) {
		//cout << "error" << '\n';
		Loc tmp = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			if (xx<1 || xx>n || yy<1 || yy>m) continue;
			
			if (map[xx][yy] == 0 && ch[xx][yy][tmp.z][1-tmp.night] == 0) {
				ch[xx][yy][tmp.z][1-tmp.night] = ch[tmp.x][tmp.y][tmp.z][tmp.night] + 1;
				Q.push(Loc(xx, yy, tmp.z,1-tmp.night));
			}
			if (tmp.z < key && map[xx][yy] == 1 && ch[xx][yy][tmp.z][1-tmp.night] == 0 && tmp.night==0) {
				ch[xx][yy][tmp.z + 1][1-tmp.night] = ch[tmp.x][tmp.y][tmp.z][tmp.night] + 1;
				Q.push(Loc(xx, yy, tmp.z + 1,1-tmp.night));
			}
		}
		if (ch[tmp.x][tmp.y][tmp.z][1 - tmp.night] == 0) {
			ch[tmp.x][tmp.y][tmp.z][1 - tmp.night] = ch[tmp.x][tmp.y][tmp.z][tmp.night] + 1;
			Q.push(Loc(tmp.x, tmp.y, tmp.z, 1 - tmp.night));
		}
	}
	int cnt = 2147000000;
	for (int j = 0; j < 2; j++) {
		for (int i = 0; i <= key; i++) {
			if (ch[n][m][i][j] != 0) cnt = min(cnt, ch[n][m][i][j]);
		}
	}
	if (cnt == 2147000000) cout << "-1" << '\n';
	else cout << cnt << '\n';
	return 0;
}