예제 입력 1
1 4 1
0010
예제 출력 1
5
예제 입력 2
1 4 1
0100
예제 출력 2
4
예제 입력 3
6 4 1
0100
1110
1000
0000
0111
0000
예제 출력 3
15
예제 입력 4
6 4 2
0100
1110
1000
0000
0111
0000
예제 출력 4
9
https://www.acmicpc.net/problem/16933
- 추가된 조건은, 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다를 처리해 주어야 한다. 처음에는 해당 조건을 처리하기 위해 현재 밤일 경우 다음 칸의 밤 이동 거리를 + 2 해주었는데 정답이 아닌듯. 그냥 가만히 있는 경우로 처리 하여야 한다.
// 가만히 있는게 가능할 경우
if (dist[now.r][now.c][now.k][!now.night] == 0)
{
dist[now.r][now.c][now.k][!now.night] = dist[now.r][now.c][now.k][now.night] + 1;
now.night = !now.night;
q.push(now);
}
#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
constexpr int MAX_SIZE = 1000;
constexpr int MAX_QUEUE_SIZE = MAX_SIZE * 100;
constexpr int MAX_BRAKE_SIZE = 11;
int R, C, K;
int map[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE][MAX_BRAKE_SIZE][2];
int dR[] = { -1, 1, 0, 0 };
int dC[] = { 0, 0, -1, 1 };
class Point
{
public:
int r;
int c;
int k;
bool night;
Point() {}
Point(int r, int c, int k, bool night) : r(r), c(c), k(k), night(night) {}
bool IsInBoundary(int R, int C)
{
return (r >= 0) && (r < R) && (c >= 0) && (c < C);
}
bool operator==(Point other)
{
return (r == other.r) && (c == other.c);
}
};
template <typename T>
class Queue
{
private:
int front;
int rear;
T items[MAX_QUEUE_SIZE];
public:
Queue() {
front = rear = 0;
}
void push(T item)
{
items[rear] = item;
rear = (rear + 1) % MAX_QUEUE_SIZE;
}
T pop()
{
T result = items[front];
front = (front + 1) % MAX_QUEUE_SIZE;
return result;
}
bool isEmpty() { return front == rear; }
};
Queue<Point> q;
void BFS()
{
int ans = -1;
Point target(R-1, C-1, 0, 0);
Point start(0, 0, 0, false);
dist[0][0][0][false] = 1;
q.push(start);
while (!q.isEmpty())
{
Point now = q.pop();
if (now == target)
{
if (ans == -1) ans = dist[now.r][now.c][now.k][now.night];
else ans = MIN(ans, dist[now.r][now.c][now.k][now.night]);
}
for (int i = 0; i < 4; i++)
{
Point next(now.r + dR[i], now.c + dC[i], now.k, !now.night);
if (!next.IsInBoundary(R, C)) continue;
if (dist[next.r][next.c][next.k][next.night] == 0 && map[next.r][next.c] == 0)
{
dist[next.r][next.c][next.k][next.night] = dist[now.r][now.c][now.k][now.night] + 1;
q.push(next);
}
// 부순 뒤에는 낮이 되어야 한다.
else if (next.k + 1 <= K && next.night == true && dist[next.r][next.c][next.k + 1][next.night] == 0 && map[next.r][next.c] == 1)
{
next.k++;
dist[next.r][next.c][next.k][next.night] = dist[now.r][now.c][now.k][now.night] + 1;
q.push(next);
}
}
// 가만히 있는게 가능할 경우
if (dist[now.r][now.c][now.k][!now.night] == 0)
{
dist[now.r][now.c][now.k][!now.night] = dist[now.r][now.c][now.k][now.night] + 1;
now.night = !now.night;
q.push(now);
}
}
printf("%d\n", ans);
}
int main(void)
{
scanf("%d %d %d", &R, &C, &K);
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
scanf("%1d", &map[i][j]);
}
}
BFS();
return 0;
}
'Algorithm > 문제풀이' 카테고리의 다른 글
[BFS] 탈출 (0) | 2019.10.24 |
---|---|
[BFS] 움직이는 미로 탈출 (0) | 2019.10.23 |
[BFS] 벽 부수고 이동하기 2 (0) | 2019.10.16 |
[BFS ] 벽 부수고 이동하기 4 (0) | 2019.10.16 |
[BFS] 벽 부수고 이동하기 (0) | 2019.10.15 |