16933 벽 부수고 이동하기 3

벽을 부수는 옵션 이외에 낮과 밤을 두어 낮에만 벽을 부술 수 있는 옵션이 추가되었다. 따라서 좌표 이외에 벽을 부순 횟수와 낮과 밤을 구분할 수 있는 배열 요소를 추가해서 접근하도록 한다

 

1. 가만 있을 때

낮과 밤을 바꿔, 이동했는지 체크

2. 빈칸으로 이동할 때

낮과 밤을 바꿔, 이동했는지 체크

3. 벽으로 이동할 때

낮과 밤을 바꾸면서, 벽을 부술 수 있는지와 전에 이동했는지 체크

 

문제: https://www.acmicpc.net/problem/16933

깃허브주소: https://github.com/surinoel/boj/blob/master/16933.cpp

 

	#include <queue>
	#include <tuple>
	#include <string>
	#include <cstring>
	#include <iostream>
	using namespace std;
	int mat[1001][1001];
	int d[1001][1001][11][2];
	struct MAT {
	int x, y, k, b;
	MAT(int x = 0, int y = 0, int k = 0, int b = 0) :
	x(x), y(y), k(k), b(b) {}
	};
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, tk;
	cin >> n >> m >> tk;
	for (int i = 1; i <= n; i++) {
	string s;
	cin >> s;
	for (int j = 1; j <= m; j++) {
	mat[i][j] = s[j - 1] - '0';
	}
	}
	memset(d, -1, sizeof(d));
	queue<MAT> q;
	q.push(MAT(1, 1, 0, 0));
	d[1][1][0][0] = 1;
	while (!q.empty()) {
	int x, y, k, b;
	x = q.front().x;
	y = q.front().y;
	k = q.front().k;
	b = q.front().b;
	q.pop();
	for (int u = 0; u < 4; u++) {
	int tx = x + dx[u];
	int ty = y + dy[u];
	int tb = (b + 1) % 2;
	if (tx < 1 || ty < 1 || tx > n || ty > m) continue;
	if (d[x][y][k][tb] == -1) {
	d[x][y][k][tb] = d[x][y][k][b] + 1;
	q.push(MAT(x, y, k, tb));
	}
	if (mat[tx][ty] == 0 && d[tx][ty][k][tb] == -1) {
	d[tx][ty][k][tb] = d[x][y][k][b] + 1;
	q.push(MAT(tx, ty, k, tb));
	}
	else if (mat[tx][ty] == 1) {l
	if (b == 0 && k + 1 <= tk && d[tx][ty][k + 1][tb] == -1) {
	d[tx][ty][k + 1][tb] = d[x][y][k][b] + 1;
	q.push(MAT(tx, ty, k + 1, tb));
	}
	}
	}
	}
	int ans = -1;
	for (int i = 0; i <= tk; i++) {
	for (int j = 0; j < 2; j++) {
	if (ans == -1 || (d[n][m][i][j] != -1 && ans > d[n][m][i][j])) {
	ans = d[n][m][i][j];
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw 16933.cpp hosted with ❤ by GitHub