2589번: 보물섬

https://www.acmicpc.net/problem/2589


$O(n^2m^2)$

육지인 각 지점마다 BFS를 이용해 다른 지점까지의 최단 거리를 구하고 그 중 최댓값을 출력한다.

#include<cstdio>
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, m, qx[2500], qy[2500], r;
char str[50][51];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (str[i][j] == 'L') {
            int h = 0, t = 1, ck[50][50] = { 0, };
            qx[0] = i; qy[0] = j;
            ck[i][j] = 1;
            while (h^t) {
                for (int k = 0; k < 4; k++) {
                    int tx = qx[h] + fx[k], ty = qy[h] + fy[k];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m || str[tx][ty] == 'W' || ck[tx][ty]) continue;
                    ck[tx][ty] = ck[qx[h]][qy[h]] + 1;
                    if (ck[tx][ty] - 1>r) r = ck[tx][ty] - 1;
                    qx[t] = tx; qy[t++] = ty;
                }
                h++;
            }
        }
    }
    printf("%d", r);
    return 0;
}