static int N, M;
static char board[2000][2000];
static char ans[4096];
static int visit[2000][2000];
static queue<pair<int, int>> q[2];
static void solution(void)
{
int len = 0, y = 0, x = 0, turn = 0;
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%s\n", board[i]);
ans[len++] = board[0][0];
q[turn].push(pair<int, int>(0, 0));
while (len < N + M - 2)
{
char min = 0x7f;
if (q[turn].size() == 1)
{
pair<int, int> cur = q[turn].front();
q[turn].pop();
y = cur.first; x = cur.second;
char d = 0x7f, r = 0x7f;
if (y + 1 < N && x < M)
d = board[y + 1][x];
if (x + 1 < M && y < N)
r = board[y][x + 1];
if (d < r)
{
ans[len++] = d;
q[1 - turn].push(pair<int, int>(y + 1, x));
}
else if (d > r)
{
ans[len++] = r;
q[1 - turn].push(pair<int, int>(y, x + 1));
}
else
{
ans[len++] = d;
q[1 - turn].push(pair<int, int>(y, x + 1));
q[1 - turn].push(pair<int, int>(y + 1, x));
}
}
else
{
while (!q[turn].empty())
{
pair<int, int> cur = q[turn].front();
q[turn].pop();
y = cur.first; x = cur.second;
char d = 0x7f, r = 0x7f;
if (y + 1 < N && x < M)
d = board[y + 1][x];
if (x + 1 < M && y < N)
r = board[y][x + 1];
if (r != 0x7f && r <= min)
{
if (r < min)
{
min = r;
while (!q[1 - turn].empty())
q[1 - turn].pop();
}
if (!visit[y][x + 1])
{
q[1 - turn].push(pair<int, int>(y, x + 1));
visit[y][x + 1] = 1;
}
}
if (d != 0x7f && d <= min)
{
if (d < min)
{
min = d;
while (!q[1 - turn].empty())
q[1 - turn].pop();
}
if (!visit[y + 1][x])
{
q[1 - turn].push(pair<int, int>(y + 1, x));
visit[y + 1][x] = 1;
}
}
}
ans[len++] = min;
}
turn = 1 - turn;
}
ans[N + M - 2] = board[N - 1][M - 1];
ans[N + M - 1] = 0;
printf("%s\n", ans);
for (int i = 0; i < 2; i++)
while (!q[i].empty())
q[i].pop();
memset(visit, 0, sizeof(visit));
}
이 문제는 단순하게 재귀로 풀면(dfs 같은 방식) 답은 구할 수 있지만, 타임아웃이 발생하게 된다.
아래의 예제(b b b b b...)에 대해서 생각해보면 이는 충분히 맞는 얘기이다.
그래서 다른 방법을 생각해야 했다.
위 코드는 다음과 같은 방식으로 동작한다.
1. 현재 위치에서 오른쪽, 아래쪽 둘 중 하나만 최소값임이 보장되면 그 길로 간다.
2. 현재 위치에서 오른쪽, 아래쪽이 같은 값이라서 최소값을 찾을 수 없을 경우 두 경로 모두 가고, 이동한 위치 들에서 오른쪽, 아래쪽 중 최소 값을 찾는다. 그리고, 이러한 작업이 계속 반복 된다면 중복되는 경로가 없게 해야한다.
저 중복경로를 해결하기 위해 처음 생각한 방식은
우상단에서 좌하단으로 내려 가능 경로에서 오른쪽 경로를 확인 하는 것은 우상단의 경로에서만 하도록 하였다.
이렇게 한 이유는 아래 경우에 대해서 어떻게 해결할 지 고민을 하였기 때문이다.
b b b b b
b b b b b
b b b b b
b b b b b
b b b b b
이런 경우라면 좌하단으로 내려가는 경로에서 해당 위치는 굳이 오른쪽을 볼 필요 가 없게 된다. 앞선 경로에서 아래쪽이 곧 현재 경로에서 오른쪽이 되기 때문이다.
하지만 이는 잘못된 방식이다. 아래의 경우를 만족하지 못하기 때문이다.
b b b b b
b b b b b
b b c b b
b b a b b
b b b b b
이런 경우라면 b입장에서는 본인보다 뒷서는 c를 고민 하지 않게 된다. 여기 까지는 맞다.
그러나 오른쪽에 a가 있는 b에 위치에서는 a로 갈 수 없게 되기 때문에 위 방법이 잘못 된 방법이라는 것이다.
마지막은 답이 되는 문자열의 길이에 대한 것이다.
이는 위 예제를 통해 쉽게 알 수 있다.
(가로 + 세로 - 1), 오른쪽으로만 가고 왼쪽으로 만 가는 경로의 길이다.