백준(BOJ) 14442번 벽 부수고 이동하기 2

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

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

 

풀이 :

 

q에 들어갈 요소는 y , x 값과 K의 값이다. 상하좌우로 방문하면서 벽에 방문하더라도 K의 값을 깍으면서 진행

 

할 수 있도록 만들자.

 

 

코드 ( C++ )

	#include <iostream>
	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	int N, M, K;
	string map[1000];
	vector<pair<int, int>> v;
	int dis[1001][1001][11];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int BFS()
	{
	queue<pair<pair<int, int>,int>> q;
	q.push({ { 0,0 },K });
	dis[0][0][K] = 1;
	while (!q.empty())
	{
	int y = q.front().first.first;
	int x = q.front().first.second;
	int cnt = q.front().second;
	q.pop();
	for (int i = 0; i < 4; ++i)
	{
	int ny = y + dy[i];
	int nx = x + dx[i];
	if (!(ny >= 0 && ny < N && nx >= 0 && nx < M)) continue;
	if (dis[ny][nx][cnt] == 0 && map[ny][nx] == '0') {
	dis[ny][nx][cnt] = dis[y][x][cnt] + 1;
	q.push({ { ny,nx }, cnt });
	}
	if (cnt > 0 && map[ny][nx] == '1' && dis[ny][nx][cnt - 1] == 0) {
	dis[ny][nx][cnt - 1] = dis[y][x][cnt] + 1;
	q.push({ {ny,nx}, cnt - 1 });
	}
	}
	}
	int ret = -1;
	for (int i = 0; i <= K; ++i) {
	if (dis[N - 1][M - 1][i] == 0) continue;
	if (ret == -1) {
	ret = dis[N - 1][M - 1][i];
	}
	else if (ret > dis[N - 1][M - 1][i]) {
	ret = dis[N - 1][M - 1][i];
	}
	}
	return ret;
	}
	int main()
	{
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i)
	cin >> map[i];
	cout << BFS() << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub