1981번: 배열에서 이동

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


$O(an^2)$ // a:배열에 있는 숫자 중 가장 큰 값, 에커먼 함수값을 상수 취급

각각의 하한값 0~200에 대해 상한값을 올려가며 그 사이의 지점들을 union-find를 이용해 합친다.
시작지점과 끝지점이 같은 집합에 있다면 제한 범위 내에 갈 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, cnt, p[10000], r = 999;
pair<int, int> s[10000];
int f(int h) { return h^p[h] ? p[h] = f(p[h]) : h; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) s[cnt].second = i*n + j, scanf("%d", &s[cnt++].first);
    sort(s, s + cnt);
    for (int i = 0; i <= 200; i++) {
        int ck[100][100] = { 0, };
        for (int j = 0; j < n*n; j++) p[j] = j;
        for (int j = 0; j < cnt; j++) if (s[j].first >= i) {
            ck[s[j].second / n][s[j].second%n] = 1;
            for (int k = 0; k < 4; k++) {
                int tx = s[j].second / n + fx[k], ty = s[j].second%n + fy[k];
                if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty]) p[f(tx*n + ty)] = f(s[j].second);
            }
            if (f(0) == f(n*n - 1)) { r = min(r, s[j].first - i); break; }
        }
    }
    printf("%d", r);
    return 0;
}