记录编号	192604	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1458]牛奶瓶编号	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.921 s
提交时间	2015-10-11 21:54:32	内存使用	0.29 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=30;
typedef long long LL;
int N;
int P[SIZEN][SIZEN];
bool use[SIZEN];//第i个记录是否被使用
int ans[SIZEN][SIZEN],nowans[SIZEN][SIZEN];
int hang[SIZEN],lie[SIZEN];
deque<int> s[SIZEN];
bool co[SIZEN],ok;
bool read()
{
	char str[SIZEN][SIZEN];
	scanf("%d",&N);
	if(N==0) return 0;
	for(int i=1;i<=2*N;i++)
		scanf("%s",str[i]);
	ok=0;memset(hang,0,sizeof(hang));memset(lie,0,sizeof(lie));
	memset(P,0,sizeof(P));
	memset(use,0,sizeof(use));
	memset(ans,0,sizeof(ans));
	memset(nowans,0,sizeof(nowans));
	for(int i=1;i<=2*N;i++) for(int j=0;j<N;j++) P[i][j+1]=str[i][j]-'0';
	return 1;
}
bool pan(int i,int j)//第i条信息是否能与第j列匹配
{
	for(int k=1;k<=N;k++) if(P[i][k]!=2&&nowans[k][j]!=2&&P[i][k]!=nowans[k][j]) return 0;
	return 1;
}
bool makegragh()
{
	bool now=0;
	for(int i=1;i<=2*N;i++) s[i].clear();
	for(int i=1;i<=2*N;i++)
		if(!use[i])
		{
			now=0;
			for(int j=1;j<=N;j++) if(pan(i,j)) {s[i].push_back(j);now=1;}
			if(now==0) return 0;
		}
	return 1;
}
bool find(int x)
{
	for(int i=0;i<s[x].size();i++)
	{
		int w=s[x][i];
		if(!co[w])
		{
			co[w]=1;
			if(!lie[w]||find(lie[w]))
			{
				lie[w]=x;
				return 1;
			}
		}
	}
	return 0;
}
LL cnt2=0;
bool match()
{
	if(!makegragh()) return 0;
	int now=0;
	cnt2++;
	for(int i=1;i<=2*N;i++)
	{
		if(!use[i])
		{
			memset(co,0,sizeof(co));
			if(find(i)) now++;
		}
	}
	if(now==N) return 1;
	memset(lie,0,sizeof(lie));
	return 0;
}
void make_ans()
{
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) ans[i][j]=nowans[i][j];
	for(int i=1;i<=N;i++)
	{
		int x=lie[i];
		for(int j=1;j<=N;j++) if(ans[j][i]==2) ans[j][i]=P[x][j];
	}
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(ans[i][j]==2) ans[i][j]=0;
}
LL cnt=0;
void dfs(int x)
{
	if(ok==1) return;
	if(x==N+1)
	{
		cnt++;
		if(match()) {ok=1;make_ans();}
		return;
	}
	for(int i=1;i<=2*N;i++)
	{
		if(!use[i]) 
		{
			hang[x]=i;use[i]=1;for(int j=1;j<=N;j++) nowans[x][j]=P[i][j];
			dfs(x+1);
			if(ok==1) break;
			hang[x]=0;use[i]=0;for(int j=1;j<=N;j++) nowans[x][j]=0;
		}
	}
}
void work()
{
	dfs(1);
	if(ok==0) {printf("0");return;}
	printf("  ");
	for(int i=1;i<=N;i++) printf("%d ",lie[i]);
	printf("\n");
	for(int i=1;i<=N;i++)
	{
		printf("%d ",hang[i]);
		for(int j=1;j<=N;j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
}
int main()
{
	freopen("milkdate.in","r",stdin);
	freopen("milkdate.out","w",stdout);
	while(read()) work();
	return 0;
}