30294 - Flea

문제 번역

$N*M$크기의 격자 칸에 벼룩을 잡기 위한 트랩을 만들어 두었습니다. 이 트랩에는 약한 방향(상, 하, 좌, 우)이 있어 해당 방향으로 벼룩이 도망갈 수 있습니다. 벼룩의 최대 점프력은 $K$입니다. 벼룩이 $N*M$ 칸을 벗어나면 탈출했다고 표현합니다.

벼룩이 여러 번 점프를 해서 탈출할 수 있는 칸의 개수를 모두 구하십시오.

step 1

각 격자칸을 정점으로 생각합니다. 벼룩이 칸 $A$에서 칸$B$로 이동할 수 있다면 $B$에서 $A$로 가는 간선을 그려줍니다. 탈출할 수 있는 칸을 전부 구한 다음 그 위치에서 BFS를 돌리면 답을 구할 수 있습니다.

step 2

각 칸마다 $K$개의 간선이 나올 수 있으므로 $N*M*K$의 시간이 필요합니다. 하지만 이러면 시간초과가 나옵니다.

다음과 같은 상황을 생각해 봅시다.

6번째 칸에서 2번짜 칸으로 가는 간선은 만들어 줄 필요가 없습니다. 6 -> 3 -> 2를 통해 도달할 수 있기 때문이죠. 즉,

1. 왼쪽으로 쭉 보면서 간선을 연결해 줍니다.
2. L을 만나면 그 칸 까지만 연결하고 더이상 연결하지 않습니다.

이 과정을 L, R, U, D에 대해 다 해주면 됩니다. 그럼 $N*M$에 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> v[4000100];
char mapp[3000][3000];
int ch[4000100];
int n, m;
queue<int> q;
int en(int x, int y) {
    return (x - 1) * m + y;
}
int main() {
    int d,i,j,k,cnt=0;
    scanf("%d%d%d", &n, &m, &d);
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= m;j++) {
            scanf(" %c", &mapp[i][j]);
        }
    }
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= m;j++) {
            if (mapp[i][j] == 'L') {
                for (k = 1;k <= d;k++) {
                    if (j - k == 0) break;
                    v[en(i, j - k)].push_back(en(i, j));
                    if (mapp[i][j - k] == 'L') break;
                }
            }
        }
    }
    for (i = 1;i <= n;i++) {
        for (j = m;j >= 1;j--) {
            if (mapp[i][j] == 'R') {
                for (k = 1;k <= d;k++) {
                    if (j + k > m) break;
                    v[en(i, j + k)].push_back(en(i, j));
                    if (mapp[i][j + k] == 'R') break;
                }
            }
        }
    }
    for (i = 1;i <= m;i++) {
        for (j = 1;j <= n;j++) {
            if (mapp[j][i] == 'U') {
                for (k = 1;k <= d;k++) {
                    if (j - k <= 0) break;
                    v[en(j - k, i)].push_back(en(j, i));
                    if (mapp[j - k][i] == 'U') break;
                }
            }
        }
    }
    for (i = 1;i <= m;i++) {
        for (j = n;j >= 1;j--) {
            if (mapp[j][i] == 'D') {
                for (k = 1;k <= d;k++) {
                    if (j + k > n) break;
                    v[en(j + k, i)].push_back(en(j, i));
                    if (mapp[j + k][i] == 'D') break;
                }
            }
        }
    }
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= m;j++) {
            if (mapp[i][j] == 'U' && i <= d) { q.push(en(i, j)); ch[en(i,j)] = 1; }
            if (mapp[i][j] == 'D' && i > n-d) { q.push(en(i, j)); ch[en(i, j)] = 1; }
            if (mapp[i][j] == 'L' && j <= d) { q.push(en(i, j)); ch[en(i, j)] = 1; }
            if (mapp[i][j] == 'R' && j > m-d) { q.push(en(i, j)); ch[en(i, j)] = 1; }
        }
    }
    while (q.size()) {
        cnt++;
        int i = q.front();
        q.pop();
        for (j = 0;j < v[i].size();j++) {
            if (ch[v[i][j]] == 1) continue;
            ch[v[i][j]] = 1;
            q.push(v[i][j]);
        }
    }
    printf("%d", cnt);
    return 0;
}