Submission #1190815

---

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 {
        if (spec == r.spec && y == r.y) {
            return x < r.x;
        }
        if (spec == r.spec) {
            return y < r.y;
        }
        return spec < r.spec;
    }
    bool operator==( const node& r ) const {
        return y == r.y && x == r.x;
    }
    bool operator!=( const node& r ) const {
        return y != r.y || x != r.x;
    }
};

map<node, node> par;
node last;

bool isOk(map<int,map<int,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;
}

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

bool search(node n, int depth, map<int,map<int,int> > &tmp_used) {
    if (depth==K) {
        last = n;
        //std::cout << "end" << endl;
        //REP(i,K) {
        //    cout << last.y << ", " << last.x << endl;
        //    last = par[last];
        //}
        //last = n;
        return true;
    }
    priority_queue<node> q;
    REP(i, 4) {
        int ny = n.y + dy[i];
        int nx = n.x + dx[i];
        node nex = node{ny,nx,0};
        if (isOk(tmp_used, nex)) {
            nex.spec = field[ny][nx]-'0';
            q.push(nex);
        }
    }
    while(!q.empty()) {
        node nex = q.top();q.pop();
        par[nex] = n;
        map<int,map<int,int> > tu = tmp_used;
        tu[nex.y][nex.x] = 1;
        // cout << n.y << ", " << n.x << " to " << nex.y << ", " << nex.x << endl;
        if (search(nex, depth+1, tu)){
            return true;
        }
    }
    return false;
}

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;
        map<int,map<int,int> > tu;
        tu[a.y][a.x] = 1;
        if (search(a,1,tu)) {
            REP(i,K) {
                ans.insert(last);
                used[last.y][last.x] = 1;
                last = par[last];
            }
            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