[BOJ] 2842 : 집배원 한상덕

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int dx[] = { 0,0,-1,1,-1,-1,1,1 };
const int dy[] = { -1,1,0,0,-1,1,-1,1 };

int n, sx, sy, k, b[55][55], chk[55][55];
char a[55][55];
vector<int> v;

int dfs(int x, int y, int mn, int mx) {
    if (chk[x][y] ||
        b[x][y] < mn || mx < b[x][y] ||
        x < 1 || n < x || y < 1 || n < y) {
        return 0;
    }
    chk[x][y] = 1;
    int ret = 0;
    if (a[x][y] == 'K') {
        ret++;
    }
    for (int i = 0; i < 8; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        ret += dfs(nx, ny, mn, mx);
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", a[i]+1);
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 'P') {
                sx = i, sy = j;
            }
            if (a[i][j] == 'K') {
                k++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &b[i][j]);
            v.push_back(b[i][j]);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int i, j = 0, ans = 1e9;
    for (i = 0; i < v.size(); i++) {
        while (1) {
            memset(chk, 0, sizeof(chk));
            if (dfs(sx, sy, v[j], v[i]) != k) {
                break;
            }
            ans = min(ans, v[i]-v[j]);
            j++;
        }
    }

    printf("%d", ans);

    return 0;
}