백준 소스코드 [C++] 16933 벽 부수고 이동하기 3

www.acmicpc.net/problem/16933

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

백준 소스코드 [C++] 16933 벽 부수고 이동하기 3

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

#define dot first
#define flag second
int n, m, k;
int arr[1002][1002];
int dist[1002][1002][11];
struct dots {
	int y, x, chk, cost,night;
};

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
void bfs() {
	queue<dots> q;
	q.push({ 1,1,0,1,0 });
	while (q.empty() != true) {
		dots n = q.front();
		q.pop();
		for (int i = 0;i < 4;i++) {
			if (arr[n.y + dy[i]][n.x + dx[i]] == 1) {
				if(n.night==1)
					q.push({ n.y ,n.x ,n.chk ,n.cost +1, abs(n.night - 1) });
				else if (n.chk < k && n.cost + 1 < dist[n.y + dy[i]][n.x + dx[i]][n.chk+1]) {
					dist[n.y + dy[i]][n.x + dx[i]][n.chk+1] = n.cost + 1;
					q.push({ n.y + dy[i],n.x + dx[i],n.chk+1,n.cost + 1 ,abs(n.night - 1) });
				}
			}
			else if (arr[n.y + dy[i]][n.x + dx[i]] == 0) {
				if (n.cost + 1 < dist[n.y + dy[i]][n.x + dx[i]][n.chk]) {
					dist[n.y + dy[i]][n.x + dx[i]][n.chk] = n.cost + 1;
					q.push({ n.y + dy[i],n.x + dx[i],n.chk,n.cost + 1 ,abs(n.night-1)});
				}
			}
		}
	}
	int mini = INT_MAX;
	for (int i = 0;i <= k;i++) mini = min(mini, dist[n][m][i]);

	if (mini < INT_MAX) cout << mini;
	else cout << "-1";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	string s;
	for (int i = 0;i <= n + 1;i++)
		for (int j = 0;j <= m + 1;j++)
			arr[i][j] = 2;

	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			for (int h = 0;h <= k;h++)
			dist[i][j][h] = INT_MAX;

	for (int i = 0;i <= k;i++) dist[1][1][i] = 1;

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

	bfs();
	return 0;
}