Submission #2087443

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int mp[51][51];
bool used[51][51];
vector<pint> v[4][500];
int cp[4];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int main(){
    int h,w,k;
    cin>>h>>w>>k;
    int cnt=0;
    string si;
    rep(i,h){
        cin>>si;
        rep(j,w) mp[i][j]=si[j]-'0';
    }
    rep(p,4){
        cnt=0;
        memset(used,0,sizeof(used));
        rep(y,h)rep(x,w){
        if(used[y][x]&&mp[y][x]==0) continue;
        queue<pair<pint,int> > q;
        q.push({{x,y},0});
        used[y][x]=true;
        while(!q.empty()){
            pair<pint,int> pi=q.front();q.pop();
            int mx=0,nx=-1,ny=-1;
            rep(i,4){
                int tx=pi.first.first+dx[(i+p)%4],ty=pi.first.second+dy[(i+p)%4];
                if(tx>=0&&ty>=0&&tx<w&&ty<h&&mp[ty][tx]!=0&&!used[ty][tx]){ 
                    if(mx<mp[ty][tx]) mx=mp[ty][tx],nx=tx,ny=ty;
                }   
            }
            if(mx==0){
                for(auto it:v[p][cnt]){
                    used[it.second][it.first]=false;
                }
                v[p][cnt].clear();
                break;
            }
            q.push({{nx,ny},pi.second+1});
            v[p][cnt].pb(nx,ny);
            used[ny][nx]=true;
            if(v[p][cnt].size()==k){
                ++cnt;
                break;
            }
        }
        }
        cp[p]=cnt;
    }
    ll mx=0;
    int tg;
    rep(i,4){
        ll sum=0;
        rep(j,cp[i]){
            ll mul=1;
            rep(q,k){
                mul*=mp[v[i][j][q].second][v[i][j][q].first];
            }
            sum+=mul;
        }
        if(mx<sum) mx=sum,tg=i;
    }
    cout<<cp[tg]<<endl;
    rep(i,cp[tg]){
        rep(j,k){
            cout<<v[tg][i][j].second+1<<" "<<v[tg][i][j].first+1<<endl;
        }
    }
    return 0;
}

Submission Info

Judge Result