Accepted/16904 kb/1112 ms

3109.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//...
char s[5];
//...
int Big[10][10][10],pos;
//...
int Solute[10][400000],f[10],vis[10];
int h[10][10],l[10][10],ten[10],xx[10],yy[10];
bool chk(int p,int x,int y,int i)
{
	for (int j=x;j<=x+2;j++)
		for (int k=y;k<=y+2;k++)
		{
			int v=Solute[p][i]/ten[9-(j-x)*3-(k-y)-1]%10;
			if (h[j][v] || l[k][v]) return false;
		}
	return true;
}
void add(int p,int x,int y,int i,int f)
{
	for (int j=x;j<=x+2;j++)
		for (int k=y;k<=y+2;k++)
		{
			int v=Solute[p][i]/ten[9-(j-x)*3-(k-y)-1]%10;
			h[j][v]=l[k][v]=f;
		}
}
void dfs1(int p,int now)
{
	if (p>9)
	{
		for (int i=1;i<=9;i++)
		{
			if ((f[1]>f[2])^(Big[i][1][2])) continue;
			if ((f[2]>f[3])^(Big[i][2][3])) continue;
			if ((f[1]>f[4])^(Big[i][1][4])) continue;
			if ((f[2]>f[5])^(Big[i][2][5])) continue;
			if ((f[3]>f[6])^(Big[i][3][6])) continue;
			if ((f[4]>f[5])^(Big[i][4][5])) continue;
			if ((f[5]>f[6])^(Big[i][5][6])) continue;
			if ((f[4]>f[7])^(Big[i][4][7])) continue;
			if ((f[5]>f[8])^(Big[i][5][8])) continue;
			if ((f[6]>f[9])^(Big[i][6][9])) continue;
			if ((f[7]>f[8])^(Big[i][7][8])) continue;
			if ((f[8]>f[9])^(Big[i][8][9])) continue;
			Solute[i][++Solute[i][0]]=now;
		}
		return;
	}
	for (int i=1;i<=9;i++)
	{
		if (!vis[i])
		{
			vis[i]=true;f[p]=i;
			dfs1(p+1,now*10+i);
			vis[i]=false;
		}
	}
}
void dfs2(int p)
{
	if (p>9)
	{
		for (int i=1;i<=9;i+=3)
			for (int j=1;j<=3;j++)
				for (int k=0;k<=2;k++)
					for (int r=1;r<=3;r++)
						printf("%d%c",Solute[i+k][f[i+k]]/ten[9-(j-1)*3-r]%10,(k==2 && r==3)?'\n':' ');
		exit(0);
	}
	int x=xx[p],y=yy[p];
	for (int i=1;i<=Solute[p][0];i++)
	{
		if (chk(p,x,y,i))
		{
			f[p]=i;
			add(p,x,y,i,1);
			dfs2(p+1);
			add(p,x,y,i,0);
		}
	}
}
int main()
{
	//Read
	for (int i=1;i<=3;i++)
	{
		for (int j=1;j<=3;j++)
		{
			pos=(i-1)*3+j;
			for (int k=1;k<=2;k++)
			{
				scanf("%s",s);
				if (s[0]=='>')
					Big[pos][k][k+1]=1;
			}
		}
		for (int j=1;j<=3;j++)
		{
			pos=(i-1)*3+j;
			for (int k=1;k<=3;k++)
			{
				scanf("%s",s);
				if (s[0]=='v')
					Big[pos][k][k+3]=1;
			}
		}
		for (int j=1;j<=3;j++)
		{
			pos=(i-1)*3+j;
			for (int k=4;k<=5;k++)
			{
				scanf("%s",s);
				if (s[0]=='>')
					Big[pos][k][k+1]=1;
			}
		}
		for (int j=1;j<=3;j++)
		{
			pos=(i-1)*3+j;
			for (int k=4;k<=6;k++)
			{
				scanf("%s",s);
				if (s[0]=='v')
					Big[pos][k][k+3]=1;
			}
		}
		for (int j=1;j<=3;j++)
		{
			pos=(i-1)*3+j;
			for (int k=7;k<=8;k++)
			{
				scanf("%s",s);
				if (s[0]=='>')
					Big[pos][k][k+1]=1;
			}
		}
	}
	//Find out solution of each block
	dfs1(1,0);
	int x=1,y=1;
	for (int i=1;i<=9;i++)
	{
		xx[i]=x;yy[i]=y;
		y+=3;
		if (y>9)
			x+=3,y=1;
	}
	ten[0]=1;
	for (int i=1;i<=9;i++)
		ten[i]=ten[i-1]*10;
	dfs2(1);
	return 0;
}