Submission #8243158

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> T;


P operator + (const P & l,const P & r){
    return {l.fs + r.fs, l.sc + r.sc};
}


class Board{
public:
    int a[32][32], h, w;
    P v[4] = {P(0, 1), P(1, 0), P(0, -1), P(-1, 0)};
    vector<T> sorted;
    bool state[32][32];
    int check[32][32];

    Board(int hh, int ww){
        h = hh; w = ww;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                a[i][j] = 0;
            }
        }
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                check[i][j] = 0;
            }
        }
    }

    void prepare(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                sorted.emplace_back(T(a[i][j], P(i, j)));
            }
        }
        sort(sorted.begin(), sorted.end());
        reverse(sorted.begin(), sorted.end());
    }

    void init(){
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                state[i][j] = false;
            }
        }
    }

    int getValue(P c){
        return a[c.fs][c.sc];
    }

    bool changeState(P x){
        state[x.fs][x.sc] = true;
    }

    bool reached(P x){
        return state[x.fs][x.sc];
    }

    P select(P c){
        P ret = P(-1, -1);
        int ma = 0;
        for(auto dir: v){
            P next = c + dir;
            if(!reached(next) && getValue(next) > ma && getValue(next) < getValue(c)){
                ret = next;
                ma = getValue(next);
            }
        }
        return ret;
    }

    vector<vector<P>> explore(){
        int su = 0;

        vector<vector<P>> res;
        vector<P> tmpPath;  tmpPath.push_back(sorted[0].sc);
        su++;

        changeState(sorted[0].sc);

        while(true) {
//            cout << su << endl;
            if(su == h * w){
                res.push_back(tmpPath);
                break;
            }

            // 探索はすでに終了
            while(true) {
                auto itr = --(tmpPath.end());

                P next = select(*itr);
                if (next.fs == -1 && next.sc == -1) {
                    // 探索終了
                    tmpPath.emplace_back(P(-1, -1));
                    break;
                }

                tmpPath.emplace_back(next);
                su++;
                changeState(next);
            }
            res.push_back(tmpPath);

            // 新たなパスを追加
            for(int i = 1; i < h * w; i++){
                if(reached(sorted[i].sc)){
                    continue;
                }
                tmpPath.clear();
                tmpPath.emplace_back(sorted[i].sc);
                changeState(sorted[i].sc);
                su++;
                break;
            }
        }

        return res;
    }

    void solve(){
        init();
        vector<vector<P>> exploreResult = explore();
        outputResult(exploreResult);

        checkResult();
    }

    int calcScore(vector<vector<int> > v){
        int res = 0;
        for(auto w: v){
            res += *w.begin();
        }
        return res;
    }

    void output(P x){
        check[x.fs][x.sc]++;
        if(x.fs != -1 && x.sc != -1) {
            cout << x.fs << " " << x.sc << endl;
        }
    }

    void outputResult(vector<vector<P>> res){
        for(auto w: res){
            vector<int> valueList;
            for(auto c: w){
                valueList.push_back(getValue(c));
            }
            while(true){
                if(valueList[0] == 0){
                    break;
                }
                valueList[0]--; output(w[0]);
                for(int i = 1; i < valueList.size(); i++){
                    if(valueList[i] == 0){
                        break;
                    }
                    if(valueList[i] == valueList[i-1]){
                        valueList[i]--;
                        output(w[i]);
                    }
                }
            }
        }
    }

    void checkResult(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                if(check[i][j] != a[i][j]){
                    cout << "check " << i << " " << j << endl;
                }
            }
        }
    }
};


int main(){
    int h = 30, w = 30;
    Board board = Board(h, w);
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> board.a[i][j];
        }
    }
    board.prepare();
    board.solve();


    return 0;
}

Submission Info

Judge Result