记录编号	385413	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1458]牛奶瓶编号	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.739 s
提交时间	2017-03-21 11:22:12	内存使用	0.29 MiB

//KZNS
#include <cstdio>
#include <cstring>
using namespace std;
#define Nmax 15
#define Mmax 25
int N, M;
char tps[Mmax][Nmax];
void init() {
	M = N*2;
	for (int i = 1; i <= M; i++)
		scanf("%s", tps[i]+1);
}
int ls[Nmax];
bool ud[Mmax];
bool gp[Mmax][Nmax];
bool makegp() {
	memset(gp, 0, sizeof(gp));
	for (int i = 1; i <= M; i++) {
		if (ud[i])
			continue;
		bool FF = false;
		for (int j = 1; j <= N; j++) {
			bool F = true;
			for (int k = 1; k <= N; k++) {
				if (!(
							tps[i][k] == '2' ||
							tps[ls[k]][j] == '2' ||
							tps[i][k] == tps[ls[k]][j]
					 )) {
					F = false;
					break;
				}
			}
			if (F) {
				FF = true;
				gp[i][j] = true;
			}
		}
		if (!FF)
			return false;
	}
	return true;
}
int py[Nmax];
bool used[Nmax];
bool find(int x) {
	for (int i = 1; i <= N; i++) {
		if (gp[x][i] && !used[i]) {
			used[i] = true;
			if (!py[i] || find(py[i])) {
				py[i] = x;
				return true;
			}
		}
	}
	return false;
}
void pf() {
	for (int i = 1; i <= N; i++)
		printf("%d ", py[i]);
	printf("\n");
	int x;
	for (int i = 1; i <= N; i++) {
		printf("%d ", ls[i]);
		x = ls[i];
		for (int j = 1; j <= N; j++) {
			if (tps[x][j] == '2')
				if (tps[py[j]][i] == '2')
					printf("0 ");
				else
					printf("%c ", tps[py[j]][i]);
			else
				printf("%c ", tps[x][j]);
		}
		printf("\n");
	}
}
bool FIND;
void KM() {
	memset(py, 0, sizeof(py));
	int cnt = 0;
	for (int i = 1; i <= M; i++) {
		if (ud[i])
			continue;
		memset(used, 0, sizeof(used));
		if (find(i))
			cnt++;
	}
	if (cnt == N) {
		pf();
		FIND = true;
	}
}
void DFS(int x) {
	if (x > N) {
		if (makegp())
			KM();
		return;
	}
	for (int i = 1; i <= M; i++) {
		if (!ud[i]) {
			ud[i] = true;
			ls[x] = i;
			DFS(x+1);
			if (FIND)
				return;
			ud[i] = false;
		}
	}
}
int main() {
	freopen("milkdate.in", "r", stdin);
	freopen("milkdate.out", "w", stdout);
	while (scanf("%d", &N), N) {
		FIND = false;
		init();
		DFS(1);
		/*
		ls[1] = 4;
		ls[2] = 10;
		ls[3] = 1;
		ls[4] = 3;
		ls[5] = 5;
		memset(ud, 0, sizeof(ud));
		ud[4] = true;
		ud[10] = true;
		ud[1] = true;
		ud[3] = true;
		ud[5] = true;
		if (makegp())
			KM();
			*/
		if (!FIND)
			printf("0\n");
	}
	return 0;
}
//UBWH