[백준] 14442번: 벽 부수고 이동하기 2

14442번: 벽 부수고 이동하기 2

 

 

#include<iostream>
#include<queue>
#define MAX 1001
using namespace std;

int n, m, k;
int map[MAX][MAX];
int visit[MAX][MAX][11];

const int dy[4] = { 1,-1,0,0 };
const int dx[4] = { 0,0,1,-1 };

int solution(int a, int b) {

	queue<pair<int,pair<int,int>>>q;
	queue<int>dis;
	q.push({ 0,{ a,b } }), dis.push(1);

	visit[a][b][0] = 1;

	while (!q.empty()) {
		int w = q.front().first;
		int y = q.front().second.first;
		int x = q.front().second.second;
		int d = dis.front();
		q.pop(), dis.pop();

		if (y == n && x == m) {
			return d;
		}

		for (int i = 0;i < 4;i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny<1 || nx<1 || ny>n || nx>m) continue;
			if (visit[ny][nx][w]) continue;
			if (map[ny][nx] == 1 && w == k) continue;

			visit[ny][nx][w] = true;

			if (map[ny][nx] == 0) q.push({ w,{ny,nx} }), dis.push(d + 1);
			if (map[ny][nx] == 1) q.push({ w + 1,{ny,nx} }), dis.push(d + 1);
		}
	}
	return -1;
}

int main() {
	cin >> n >> m >> k;

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			char c;
			cin >> c;	
			map[i][j] = c - '0';
		}
	}

	cout<<solution(1, 1);
}