2842번: POŠTAR

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

방문한 칸의 최소 높이가 x일 때 메일을 모두 보낼수 있는 방문한 칸의 최대 고도의 최솟값을 f(x)라 하자.
f(x)는 단조증가 함수가 된다. 고로 l=x, r=f(x)로 잡고 inchworm 알고리즘을 적용할 수 있다.
[l,r] 구간의 고도에 해당하는 칸만을 방문하여 모든 메일을 배달할 수 있다면 l++, 그렇지 않다면 r++을 해주며 모든 x에 대한 f(x) 값을 구한다. 답은 이러한 f(x) - x 들 중 최솟값이 된다.

시간복잡도는 $O(n^4)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int n, a[50][50], vis[50][50], sx, sy, res = 1e9, v[2500], l, r;
char s[50][51];
void f(int x, int y) {
    if (x < 0 || y < 0 || x == n || y == n || vis[x][y] || a[x][y]<v[l] || a[x][y]>v[r]) return;
    vis[x][y] = 1;
    for (int i = 0; i < 8; i++) f(x + dx[i], y + dy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j), v[i*n + j] = a[i][j];
    sort(v, v + n*n);
    while (r < n*n) {
        f(sx, sy);
        int flag = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && s[i][j] == 'K') flag = 1;
                vis[i][j] = 0;
            }
        }
        flag ? r++ : res = min(res, v[r] - v[l++]);
    }
    printf("%d", res);
    return 0;
}