Submission #3562834

---

Source Code Expand

#include <iostream>
#include <cassert>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> P;
int N = 30,A[310][310],count = 0,sum = 0;
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1},visited[31][31] = {{0}};
vector<P> ans;

void print(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			cout << A[i][j] << (j!=N? " ":"\n");
		}
	}
}

bool in(int x,int y){
	return 1<=x && x<=N && 1<=y && y<=N;
}

void init(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) visited[i][j] = 0;
	}
}

vector<P> longest(int x,int y,vector<P> v){
	visited[x][y] = 1;
	v.push_back({x,y});
	vector<P> result = v;
	if(A[x][y]==1) return result;
	for(int k=0;k<4;k++){
		int nx = x+dx[k],ny = y+dy[k];
		if(!in(nx,ny)) continue;
		if(A[x][y]-1==A[nx][ny]){
			vector<P> u = longest(nx,ny,v);
			if(result.size()<u.size()){
				result = u;
				assert(result==u);
			}
		}
	}
	return result;
}

int main(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			cin >> A[i][j];
			sum += A[i][j];
		}
	}
	priority_queue<P> Q;
	while(count<sum){
		vector<P> res;
		int s = 1e9;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				if(A[i][j]==0) continue;
				Q.push({A[i][j],31*i+j});
			}
		}
		init();
		while(!Q.empty()){
			P p = Q.top(); Q.pop();
			int x = p.second/31,y = p.second%31;
			if(visited[x][y]==1) continue;
			vector<P> a;
			vector<P> now = longest(x,y,a);
			if(s>now.size()){
				res = now;
				s = res.size();
				assert(res==now);
			}	
		}
		for(int i=0;i<res.size();i++){
			ans.push_back({res[i].first,res[i].second});
			A[res[i].first][res[i].second]--; count++;
		}
	}
	for(int i=0;i<ans.size();i++){
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}

Submission Info

Judge Result