Codeforces 45 J. Planting Trees

問題

nxmのマスに1〜nの異なる数字を、
隣接するどの2マスの数字の差も2以上であるように入れたい。

そのような入れ方を1通り出力せよ。
不可能な場合-1を出力せよ。

制約条件

n,m≦100

方針

書いて実験してみると、
(1,2),(1,3),(2,2)の場合が不可能であるが、
その他の場合は答えがあるように見える。

しかも結構自由に埋められる感じがする。
なので適当に深さ優先探索で答えを1通りだけ探してやればよい。

ソースコード

int n,m;
int ans[100][100];
bool use[10001];

bool dfs(int y,int x){
	if(x==m)return dfs(y+1,0);
	if(y==n)return 1;
	rep(i,n*m)if(!use[i+1]){
		use[i+1]=1;
		ans[y][x]=i+1;
		for(int dy=-1;dy<1;dy++)for(int dx=-1;dx<1;dx++)if(dy||dx){
			int ny=y+dy, nx=x+dx;
			if(ny<0||nx<0||dy==dx)continue;
			if(abs(ans[ny][nx]-ans[y][x])<2)goto FAIL;
		}
		if(dfs(y,x+1))return 1;
		FAIL:;
		use[i+1]=0;
	}
	return 0;
}
void run()
{
	cin>>n>>m;
	if(!dfs(0,0)){
		cout<<-1<<endl;
		return;
	}
	rep(i,n)rep(j,m)cout<<ans[i][j]<<(j==m-1?"\n":" ");
}