puzzle wall

main.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
int n, m, cnt=0;
int G[MAXN][MAXN];
int dx[] = {0,1};
int dy[] = {1,0};

bool ok(int x, int y){
	if (x<0 || x>=n) return 0;
	if (y<0 || y>=m) return 0;
	if (G[x][y]!=0)return 0;
	return 1;
}

void dfs(int idx, int x, int y){
	if (x==n){
		for (int i=0; i<n; i++){
			for (int j=0; j<m; j++){
				printf("%2d\t", G[i][j]);
			}
			puts("");
		}
		puts("");
		exit(0);
		return;
	}
	int nx = x, ny = y+1;
	if (ny==m)nx++, ny-=m;

	int r = rand()%2;
	if (ok(x,y) && ok(x+dx[r],y+dy[r])){
		G[x][y] = G[ x+dx[r] ][ y+dy[r] ] = idx;
		dfs(idx+1,nx,ny);
		G[x][y] = G[ x+dx[r] ][ y+dy[r] ] = 0;
	}
	r^=1;
	if (ok(x,y) && ok(x+dx[r],y+dy[r])){
		G[x][y] = G[ x+dx[r] ][ y+dy[r] ] = idx;
		dfs(idx+1,nx,ny);
		G[x][y] = G[ x+dx[r] ][ y+dy[r] ] = 0;
	}
	if (G[x][y]!=0)dfs(idx,nx,ny);
}

int main(){
	srand( time(NULL) );
	cin >> n >> m;
	dfs(1,0,0);
}