ตั๊กแตนในทุ่งดอกไม้: เมื่อข้อห้ามกว้างแค่สามช่อง เก็บสี่อันดับแรกก็พอ

#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> val, dp;

// สี่อันดับแรกของแต่ละแถวและแต่ละคอลัมน์ โดยดัชนีห้ามซ้ำกัน
struct Top4 {
    int v[4], k[4]; int n = 0;
    void add(int nv, int nk){
        for(int i = 0; i < n; i++) if(k[i] == nk){ if(nv > v[i]){ v[i] = nv; sortit(); } return; }
        if(n < 4){ v[n] = nv; k[n] = nk; n++; sortit(); return; }
        if(nv > v[3]){ v[3] = nv; k[3] = nk; sortit(); }
    }
    void sortit(){
        for(int i = 1; i < n; i++){ int a = v[i], b = k[i], j = i - 1;
            while(j >= 0 && v[j] < a){ v[j+1] = v[j]; k[j+1] = k[j]; j--; }
            v[j+1] = a; k[j+1] = b; }
    }
    // ห้ามได้มากสุดสามดัชนี สี่อันดับจึงเหลือรอดอย่างน้อยหนึ่งเสมอ
    int best(int b1, int b2, int b3) const {
        for(int i = 0; i < n; i++) if(k[i] != b1 && k[i] != b2 && k[i] != b3) return v[i];
        return 0;
    }
};

int main(){
    int R, C;
    if(scanf("%d %d %d", &N, &R, &C) != 3) return 0;
    R--; C--;
    val.resize((size_t)N * N); dp.assign((size_t)N * N, 0);
    for(auto &x : val) scanf("%d", &x);
    vector<int> ord((size_t)N * N);
    for(size_t i = 0; i < ord.size(); i++) ord[i] = (int)i;
    sort(ord.begin(), ord.end(), [](int a, int b){ return val[a] > val[b]; });

    vector<Top4> row(N), col(N);
    size_t i = 0;
    while(i < ord.size()){
        size_t j = i;
        while(j < ord.size() && val[ord[j]] == val[ord[i]]) j++;   // กลุ่มที่กลีบเท่ากัน
        for(size_t t = i; t < j; t++){
            int id = ord[t], r = id / N, c = id % N, best = 0;
            if(r > 0)     best = max(best, row[r-1].best(c-1, c, c+1));
            if(r + 1 < N) best = max(best, row[r+1].best(c-1, c, c+1));
            if(c > 0)     best = max(best, col[c-1].best(r-1, r, r+1));
            if(c + 1 < N) best = max(best, col[c+1].best(r-1, r, r+1));
            dp[id] = best + 1;
        }
        // ใส่เข้าตารางหลังคิดทั้งกลุ่มจบ ไม่งั้นดอกกลีบเท่ากันจะมองเห็นกันเอง
        for(size_t t = i; t < j; t++){ int id = ord[t], r = id / N, c = id % N;
            row[r].add(dp[id], c); col[c].add(dp[id], r); }
        i = j;
    }
    printf("%d\n", dp[(size_t)R * N + C]);
}

// ตัวตรวจ ไล่ดูทุกช่องบนกระดานว่ากระโดดถึงไหม ไม่มีโครงสร้างเร่งความเร็วใด ๆ
#include <bits/stdc++.h>
using namespace std;
int N, R, C; vector<vector<int>> a, memo;
int f(int r, int c){
    int &m = memo[r][c]; if(m) return m; int best = 1;
    for(int nr = 0; nr < N; nr++) for(int nc = 0; nc < N; nc++){
        if(a[nr][nc] <= a[r][c]) continue;
        int dr = abs(nr - r), dc = abs(nc - c);
        if(!((dr == 1 && dc > 1) || (dc == 1 && dr > 1))) continue;
        best = max(best, 1 + f(nr, nc));
    }
    return m = best;
}
int main(){
    scanf("%d %d %d", &N, &R, &C);
    a.assign(N, vector<int>(N)); memo.assign(N, vector<int>(N, 0));
    for(auto &row : a) for(auto &x : row) scanf("%d", &x);
    printf("%d\n", f(R - 1, C - 1));
}

// รุ่นที่ผิด ใส่ค่าเข้าตารางทันทีทีละดอก ไม่รอให้กลุ่มที่กลีบเท่ากันคิดจบก่อน
for(size_t t = i; t < j; t++){
    int id = ord[t], r = id / N, c = id % N, best = 0;
    if(r > 0)     best = max(best, row[r-1].best(c-1, c, c+1));
    if(r + 1 < N) best = max(best, row[r+1].best(c-1, c, c+1));
    if(c > 0)     best = max(best, col[c-1].best(r-1, r, r+1));
    if(c + 1 < N) best = max(best, col[c+1].best(r-1, r, r+1));
    dp[id] = best + 1;
    row[r].add(dp[id], c); col[c].add(dp[id], r);   // บรรทัดที่พัง ใส่เร็วไปหนึ่งจังหวะ
}