Submission #994869

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define N 44
int n;
int U[N], L[N], R[N], D[N];

int row[N], col[N];
bool a[N][N];

char wc[N*N]; int wn[N*N];

bool chk() {
	for (int i = 0; i < n; i ++) {
		if (U[i] + D[i] + col[i] > n) return false;
		if (L[i] + R[i] + row[i] > n) return false;
	}
	return true;
}

void ff(int t) {
	if (t == n*n) {
		for (int i = 0; i < n*n; i ++) {
			cout << wc[i] << wn[i]+1 << endl;
		}
		exit(0);
	}
	for (int i = 0; i < n; i ++) if (U[i]) {
		U[i] --;
		int x = 0;
		while (a[x][i]) x++;
		a[x][i] = 1;
		row[x] ++; col[i] ++;
		wc[t] = 'U'; wn[t] = i;
		if (chk()) ff(t+1);
		U[i] ++;
		a[x][i] = 0;
		row[x] --; col[i] --;
	}
	for (int i = 0; i < n; i ++) if (D[i]) {
		D[i] --;
		int x = n-1;
		while (a[x][i]) x--;
		a[x][i] = 1;
		row[x] ++; col[i] ++;
		wc[t] = 'D'; wn[t] = i;
		if (chk()) ff(t+1);
		D[i] ++;
		a[x][i] = 0;
		row[x] --; col[i] --;
	}
	for (int i = 0; i < n; i ++) if (L[i]) {
		L[i] --;
		int x = 0;
		while (a[i][x]) x++;
		a[i][x] = 1;
		row[i] ++; col[x] ++;
		wc[t] = 'L'; wn[t] = i;
		if (chk()) ff(t+1);
		L[i] ++;
		a[i][x] = 0;
		row[i] --; col[x] --;
	}
	for (int i = 0; i < n; i ++) if (R[i]) {
		R[i] --;
		int x = n-1;
		while (a[i][x]) x--;
		a[i][x] = 1;
		row[i] ++; col[x] ++;
		wc[t] = 'R'; wn[t] = i;
		if (chk()) ff(t+1);
		R[i] ++;
		a[i][x] = 0;
		row[i] --; col[x] --;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i ++) cin >> U[i];
	for (int i = 0; i < n; i ++) cin >> D[i];
	for (int i = 0; i < n; i ++) cin >> L[i];
	for (int i = 0; i < n; i ++) cin >> R[i];
	if (chk()) ff(0);
	puts ("NO");
	return 0;
}

Submission Info

Judge Result