Submission #1188999

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
int H, W, K;
string field[60];
int used[60][60];

struct node {
    int y, x, spec;
    bool operator<( const node& r ) const {
        return spec < r.spec;
    }
};

bool isOk(vector<vector<int> > &tmp_used, node n) {
    //　範囲外
    if (n.x < 0 || W <= n.x || n.y < 0 || H < n.y) {
        return false;
    }
    // 使用された or 数字がゼロ
    if (tmp_used[n.y][n.x] || used[n.y][n.x] || field[n.y][n.x]=='0') {
        return false;
    }
    
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> H >> W >> K;
    priority_queue<node> q;
    REP(i, H) {
        cin >> field[i];
        REP(j, W) q.push(node{(int)i,(int)j,field[i][j]-'0'});
    }
    vector< set<node> > lans;
    while(!q.empty()) {
        node a = q.top();q.pop();
        if (used[a.y][a.x]) continue;
        set<node> ans;
        ans.insert(a);
        vector<vector<int> > tmp_used(60,vector<int>(60,0));
        while(ans.size()!=K) {
            node add_node = {-1,-1,0};
            for (node b: ans) {
                REP(i,4) {
                    int nx = b.x + dx[i];
                    int ny = b.y + dy[i];
                    if (isOk(tmp_used,node{ny,nx,0})){
                        node tnode = node{ny,nx,field[ny][nx]-'0'};
                        if (add_node < tnode) {
                            add_node = tnode;
                        }
                    }
                }
            }
            if (add_node.y==-1) break;
            ans.insert(add_node);
            tmp_used[add_node.y][add_node.x] = 1;
        }
        if (ans.size()==K) {
            for (node b: ans) {
                used[b.y][b.x] = 1;
            }
            lans.pb(ans);
        }
    }
    cout << lans.size() << endl;
    for (set<node> &sn: lans) {
        for (node n: sn) {
            cout << n.y+1 << " " << n.x+1 << endl;
        }
    }
    return 0;
}

Submission Info

Judge Result