Submission #1140727

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef pair<int,int> P;
int s[50][50];
int H,W,K;
bool used[50][50];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
bool is(int x,int y){return 0<=x&&x<H&&0<=y&&y<W&&!used[x][y];}

P dfs(int x,int y,int t){	//val,hist_dir
	if(s[x][y]==0) return P(0,-1);
	if(t==K-1){
		return P(s[x][y],0);
	}
	used[x][y]=1;
	P mx(0,0);
	rep(d,4){
		int nx = x+dx[d],ny=y+dy[d];
		if(!is(nx,ny)) continue;
		P tmp = dfs(nx,ny,t+1);
		if(mx.fs<tmp.fs){
			mx=P(tmp.fs, tmp.sc*4+d);
		}
	}
	used[x][y]=0;
	mx.fs*=s[x][y];
	return mx;
}
vector<P> ans;
int main(){
	cin>>H>>W>>K;
	rep(i,H){
		string st;
		cin>>st;
		rep(j,W) s[i][j]=st[j]-'0';
	}
	while(true){
		int mx = 0;
		int si,sj;
		int hist;
		rep(i,H) rep(j,W) if(!used[i][j]){
			P tmp = dfs(i,j,0);
			int score = tmp.fs;
			if(mx<score){
				mx=score;
				si=i,sj=j;
				hist = tmp.sc;
			}
		}
		if(mx==0) break;
		P pieces[K];
		int x = si, y = sj;
		rep(i,K){
			pieces[i]=P(x,y);
			used[x][y]=1;
			if(i==K-1) break;
			int d = hist%4;
			x+=dx[d],y+=dy[d];
			hist/=4;
		}
		rep(i,K) ans.pb(pieces[i]);
	}
	cout<<ans.size()/K<<endl;
	rep(i,ans.size()) cout<<ans[i].fs+1<<" "<<ans[i].sc+1<<endl;
}

Submission Info

Judge Result