2969 - 메뚜기

 

 

step 1

꽃잎이 많은 꽃은 절대 적은 꽃으로 이동할 수 없습니다. 그럼 꽃잎 수로 정렬을 한 다음 자기보다 더 많은 꽃만 고려해도 문제를 해결할 수 있습니다. 꽃잎 수로 정렬한 다음 문제를 해결합니다.

step 2

dp[i][j] : i,j에 있는 꽃에 있을 때 이동할 수 있는 최대 횟수

 

이 dp를 어떻게든 구하면 이 문제를 해결할 수 있습니다.

아래 그림에서 검은 칸에 메뚜기가 있다고 해봅시다. 이 칸에서의 dp값은 {빨간 칸에 있는 dp값의 최대값 + 1}입니다.

 

그럼 새로운 dp를 정의해 봅시다.

 

Ldp[i][j] : i,j 포함 자기 왼쪽에 있는 모든 dp값들의 최댓값

 

이 dp를 왼쪽, 오른쪽, 위쪽, 아래쪽 모두 만들면 이 문제를 해결할 수 있습니다. 이것은 펜윅트리로 만들 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct data {
    int g,x, y;
    inline bool operator<(const data& temp)const {
        return g > temp.g;
    }
}b[2250001];
struct dp {
    int l, r, u, d;
}mapp[1501][1501];
int n;
struct dataa {
    int x, y, z;
}qu[2250001];
int find(int x, int y, int d) {
    int v = 0, p;
    if (d == 0) {
        p = y;
        while (p != 0) {
            v = max(v, mapp[x][p].l);
            p = p & (p - 1);
        }
        return v;
    }
    if (d == 2) {
        p = x;
        while (p != 0) {
            v = max(v, mapp[p][y].u);
            p = p & (p - 1);
        }
        return v;
    }
    if (d == 1) {
        p = n - y + 1;
        while (p != 0) {
            v = max(v, mapp[x][n - p + 1].r);
            p = p & (p - 1);
        }
        return v;
    }
    if (d == 3) {
        p = n - x + 1;
        while (p != 0) {
            v = max(v, mapp[n - p + 1][y].d);
            p = p & (p - 1);
        }
        return v;
    }
}
void update(int x, int y, int v) {
    int p;
    p = y;
    while (p <= n) {
        mapp[x][p].l = max(mapp[x][p].l, v);
        p = ((p | (p - 1)) + 1);
    }
    p = x;
    while (p <= n) {
        mapp[p][y].u = max(mapp[p][y].u, v);
        p = ((p | (p - 1)) + 1);
    }
    p = n - y + 1;
    while (p <= n) {
        mapp[x][n - p + 1].r = max(mapp[x][n - p + 1].r, v);
        p = ((p | (p - 1)) + 1);
    }
    p = n - x + 1;
    while (p <= n) {
        mapp[n - p + 1][y].d = max(mapp[n - p + 1][y].d, v);
        p = ((p | (p - 1)) + 1);
    }
}
int main() {
    int x, y, i,j,cnt=0,pos=1;
    scanf("%d%d%d", &n, &x, &y);
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= n;j++) {
            cnt++;
            scanf("%d", &b[cnt].g);
            b[cnt].x = i;
            b[cnt].y = j;
        }
    }
    sort(b + 1, b + cnt + 1);
    for (i = 1;i <= cnt;i++) {
        int v = 0, sx = b[i].x, sy = b[i].y;
        if (sx > 1) {
            if (sy > 2) v = max(v, find(sx - 1, sy - 2, 0));
            if (sy < n-1) v = max(v, find(sx - 1, sy + 2, 1));
        }
        if (sx < n) {
            if (sy > 2) v = max(v, find(sx + 1, sy - 2, 0));
            if (sy < n - 1) v = max(v, find(sx + 1, sy + 2, 1));
        }
        if (sy > 1) {
            if (sx > 2) v = max(v, find(sx - 2, sy - 1, 2));
            if (sx < n - 1) v = max(v, find(sx + 2, sy - 1, 3));
        }
        if (sy < n) {
            if (sx > 2) v = max(v, find(sx - 2, sy + 1, 2));
            if (sx < n - 1) v = max(v, find(sx + 2, sy + 1, 3));
        }
        if (sx == x && sy == y) {
            printf("%d", v + 1);
            return 0;
        }
        qu[i].x = sx;
        qu[i].y = sy;
        qu[i].z = v+1;
        if (b[i].g != b[i + 1].g) {
            for (int j = pos;j <= i;j++) {
                update(qu[j].x, qu[j].y, qu[j].z);
            }
            pos = i + 1;
        }
    }
    return 0;
}