BOJ 16933, 벽 부수고 이동하기 3
ProblemSolving ·이 문제는 그래프 문제입니다. 바로 전에 포스팅한 벽 부수고 이동하기 2와 유사하죠 ㅋㅋㅋㅋ.
비슷해서 포스팅안하려다가 더 푸신 분들이 적어서 포스팅합니다.
풀이
2와 다른 점이 있다면 낮에만 이동할 수 있다는 점이죠? 이것을 어떻게 처리했냐가 관건이죠
저는 cnt 이동한거리가 홀수일 때 (낮일 때) 이동했습니다. 밤일 때는 cnt만 1 증가시켜주고 자리는 그대로~
이것만 처리해준다면 이 문제도 쉽게 풀립니다 하하.
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, k;
int chk[1001][1001][11];
int a[1001][1001];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
queue <pair<pair<int, int>, pair<int, int>>> q;
int bfs(int x, int y, int cnt, int ck)
{
chk[x][y][ck] = 1;
q.push({ {x,y},{cnt + 1,ck} });
while (!q.empty())
{
x = q.front().first.first;
y = q.front().first.second;
cnt = q.front().second.first;
ck = q.front().second.second;
q.pop();
if (x == n && y == m) return cnt;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && chk[xx][yy][ck] == 0)
{
if (a[xx][yy] == 0)
{
chk[xx][yy][ck] = 1;
q.push({ {xx,yy },{cnt + 1,ck} });
}
else if (a[xx][yy] == 1 && ck < k)
{
if (cnt % 2 == 1)
{
chk[xx][yy][ck] = 1;
q.push({ {xx,yy },{cnt + 1,ck + 1} });
}
else
q.push({ {x,y },{cnt + 1,ck} });
}
}
}
}
return -1;
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%1d", &a[i][j]);
printf("%d", bfs(1, 1, 0, 0));
return 0;
}