Submission #669579

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

namespace btk{
    #define MP make_pair
    #define row second.first
    #define column second.second
    using RESULT=pair<int,pair<int,int>>;
    const int d4[]={0,-1,0,1,0};
    int cnt[30][30];
    RESULT cnt2[30][30];
    vector<pair<int,int>> getMaxLength(const vector<vector<int>>& v){
        int max_val=0;
        fill((int*)cnt,(int*)cnt+30*30,-1);
        for(int r = 0; r < 30; r++)
            for(int c = 0; c < 30; c++)
                cnt2[r][c]=RESULT(-1,MP(r,c));
        for(int r = 0; r < 30; r++)
            for(int c = 0; c < 30; c++)
                max_val=max(v[r][c],max_val);

        if(max_val==1)
            for(int r = 0; r < 30; r++)
                for(int c = 0; c < 30; c++)if(max_val==v[r][c])return vector<pair<int,int>>{MP(r,c)};

        //座標をチェックするラムダ
        auto check=[](int r,int c){return 0<=r&&r<30&&0<=c&&c<30;};

        //再帰ラムダ
        std::function<int(int,int)> dfs=[&](int r,int c){
            if(cnt[r][c]!=-1)return cnt[r][c];
            cnt[r][c]=1;
            if(v[r][c]==1)return 1;

            for(int i = 0; i < 4; i++){
                int nr=r+d4[i],nc=c+d4[i+1];
                if(check(nr,nc)&&
                    v[nr][nc]==v[r][c]-1){
                        cnt[r][c]=max(cnt[r][c],dfs(nr,nc)+1);
                    }
            }
            return cnt[r][c];
        };

        std::function<RESULT(int,int)> dfs2=[&](int r,int c){
            if(cnt2[r][c].first!=-1)return cnt2[r][c];
            cnt2[r][c].first=dfs(r,c);
            if(v[r][c]==1)return cnt2[r][c];

            for(int i = 0; i < 4; i++){
                int nr=r+d4[i],nc=c+d4[i+1];
                if(check(nr,nc)&&
                    v[nr][nc]==v[r][c]-1){
                        auto sub=dfs2(nr,nc);
                        if(sub.second==MP(nr,nc))sub.second=MP(r,c);
                        sub.first++;
                        cnt2[r][c]=max(cnt2[r][c],sub);
                    }
                if(v[r][c]>=4&&check(nr,nc)&&v[nr][nc]==v[r][c]){
                    auto sub=MP(dfs(nr,nc)+1,MP(nr,nc));
                    cnt2[r][c]=max(cnt2[r][c],sub);
                }
            }
            return cnt2[r][c];
        };
        RESULT top(-1,pair<int,int>());

        for(int r = 0; r < 30; r++)
            for(int c = 0; c < 30; c++)
                if(v[r][c]==max_val){
                    top=max(dfs2(r,c),top);
                }

        vector<pair<int,int>> res;
        res.push_back(top.second);
        while(true){
            unsigned prevsize=res.size();
            for(int i = 0; i < 4; i++){
                int nr=top.row+d4[i],nc=top.column+d4[i+1];
                if(check(nr,nc)&&
                    v[nr][nc]==v[top.row][top.column]-1&&
                    cnt[nr][nc]==cnt[top.row][top.column]-1){
                    top.second=MP(nr,nc);
                    res.push_back(top.second);
                    break;
                }
            }
            if(res.size()==prevsize)break;
        }
        return res;
    }
};

const int MAX = 30;
const int BEAM_WIDTH = 200;
int A[MAX][MAX];

struct State {
    State(int h, int w) : height(h), width(w), sum(0) {
        board.resize(height);
        for (int i = 0; i < height; i++) board[i].resize(width);
    }
    // 盤面
    vector<vector<int> > board;
    // 盤面の高さ, 幅
    int height, width;
    // 盤面の和
    int sum;
    // 評価値のメモ
    int value;
    // 評価関数
    int eval() const;
    // 今の状態で最も長い連鎖列を求める
    vector<pii> getMaxLength() const;
    // seq で与えられる操作をした際の次の状態にする
    void move(const vector<pii>& seq);
    // seq で与えられた操作をした際の状態から戻る
    void undo(const vector<pii>& seq);
    // 終わったかどうか
    bool isCleared() const ;
    bool operator<(const State& rhs) {return eval() < rhs.eval();}
    //int dfs(int y, int x) const ;
};


vector<pii> State::getMaxLength() const {
    return btk::getMaxLength(board);
}

// dp[i][j] = (i, j) 成分から動いて狭義単調減少列の最大長はいくつか
int dp[MAX][MAX];

int dfs(int y, int x, const State& state) {
    int& ret = dp[y][x];
    if (ret >= 0) return ret;
    ret = 0;
    if (state.board[y][x] == 0) return ret;
    for (int i = 0; i < 4; i++) {
        int ny = y+dy[i], nx = x+dx[i];
        if (ny < 0 || ny >= state.height || nx < 0 || nx >= state.width) continue;
        if (state.board[ny][nx] >= state.board[y][x]) continue;
        ret = max(ret, dfs(ny, nx, state));
    }
    ret++;
    return ret;
}

int State::eval() const {
    // dp を求める
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) {
        dfs(i, j, *this);
    }
    int ret = 0;
    for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) {
        ret += dp[i][j] * dp[i][j];
    }
    ret -= sum;
    return ret;
}

void State::move(const vector<pii>& seq) {
    int prev = -1;
    for (pii p : seq) {
        assert(0 <= p.first && p.first < height && 0 <= p.second && p.second < width);
        assert(prev == -1 || prev == board[p.first][p.second]+1);
        prev = board[p.first][p.second];
        board[p.first][p.second]--;
    }
    sum -= seq.size();
}

void State::undo(const vector<pii>& seq) {
    int prev = -1;
    for (pii p : seq) {
        assert(0 <= p.first && p.first < height && 0 <= p.second && p.second < width);
        assert(prev == -1 || prev == board[p.first][p.second]+1);
        prev = board[p.first][p.second];
        board[p.first][p.second]++;
    }
    sum += seq.size();
}

bool State::isCleared() const {
    return sum == 0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) {
        cin >> A[i][j];
    }
    State state(MAX, MAX);
    for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) {
        state.board[i][j] = A[i][j];
        state.sum += A[i][j];
    }
    vector<pii> ans;
    while (!state.isCleared()) {
        auto seq = state.getMaxLength();
        for (auto p : seq) ans.push_back(p);
        state.move(seq);
    }
    for (auto p : ans) {
        cout << p.first+1 << " " << p.second+1 << endl;
    }
    return 0;
}

Submission Info

Judge Result