14442번 벽 부수고 이동하기2

벽 부수고 이동하기 1보다는 어렵고 4보다는 쉽다.. 당연한 얘기ㅎ
그냥 1에서 조금만 수정해주면 된다.

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

using namespace std;
int map[1001][1001];
int ch[1001][1001][11];
int n, m, key;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct Loc {
	int x, y, z;
	Loc(int a, int b, int c) {
		x = a;
		y = b;
		z = c;
	}
};
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] = 1;
	Q.push(Loc(1, 1, 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]==0) {
				ch[xx][yy][tmp.z] = ch[tmp.x][tmp.y][tmp.z] + 1;
				Q.push(Loc(xx, yy, tmp.z));
			}
			if (tmp.z<key&&map[xx][yy] == 1&&ch[xx][yy][tmp.z]==0) {
				ch[xx][yy][tmp.z + 1] = ch[tmp.x][tmp.y][tmp.z] + 1;
				Q.push(Loc(xx, yy, tmp.z + 1));
			}

		}
	}
	int cnt = 2147000000;
	for (int i = 0; i <= key; i++) {
		if(ch[n][m][i]!=0) cnt = min(cnt, ch[n][m][i]);
	}
	if (cnt == 2147000000) cout << "-1" << '\n';
	else cout << cnt << '\n';
	return 0;
}