Description
Input
输入一共15行，包含一个新数独的实例。第奇数行包含左右方向的符号（<和>），第偶数行包含上下方向的符号（^和v）。
Output
输出包含9行，每行9个1~9的数字，以单个空格隔开。输入保证解惟一。
Sample Input
< > > < > < v v ^ ^ v v ^ ^ ^ < < > < > < ^ ^ ^ v ^ ^ ^ v v < < < < > > > < > > > > v ^ ^ ^ ^ v v v ^ > > > > < > v v ^ v ^ v ^ v ^ > < < > > > < < < < > < v ^ v v v v ^ ^ v < > > < < > ^ v v v ^ v ^ v v < > < > < >
Sample Output
4 9 1 7 3 6 5 2 8 2 3 7 8 1 5 6 4 9 5 6 8 2 4 9 7 3 1 9 1 3 6 5 4 8 7 2 8 5 4 9 7 2 1 6 3 7 2 6 3 8 1 9 5 4 3 4 9 5 6 8 2 1 7 1 8 5 4 2 7 3 9 6 6 7 2 1 9 3 4 8 5
比靶形数独那个题水多了= =……
1 #include2 #include 3 #include 4 #define id(x,y) (x-1)*9+y 5 using namespace std; 6 int Relation[101][101],ans[12][12],maxn; 7 int dx[4]= { 0,0,-1},dy[4]= { 0,-1,0}; 8 bool row[10][10],column[10][10],square[10][10][10],flag; 9 char st[101];10 11 void Dfs(int x,int y)12 {13 maxn=max(x,maxn);14 if (x==10 && y==1)15 {16 flag=true;17 for (int i=1; i<=9; ++i)18 {19 for (int j=1; j<=8; ++j)20 printf("%d ",ans[i][j]);21 printf("%d\n",ans[i][9]);22 }23 return;24 }25 int down=1,up=9;26 for (int i=1; i<=2; ++i)27 {28 int xx=x+dx[i],yy=y+dy[i];29 if (xx<1 || xx>9 || yy<1 || yy>9 || ans[xx][yy]==0) continue;30 if ( Relation[id(x,y)][id(xx,yy)] == 1 ) down=max(down,ans[xx][yy]+1);31 if ( Relation[id(x,y)][id(xx,yy)] == 0 ) up=min(up,ans[xx][yy]-1);32 }33 for (int i=down; i<=up; ++i)34 if (!row[x][i] && !column[y][i] && !square[(x-1)/3][(y-1)/3][i])35 {36 ans[x][y]=i;37 row[x][i]=column[y][i]=square[(x-1)/3][(y-1)/3][i]=true;38 if (y==9) Dfs(x+1,1);39 else Dfs(x,y+1);40 ans[x][y]=0;41 row[x][i]=column[y][i]=square[(x-1)/3][(y-1)/3][i]=false;42 43 if (flag) return;44 }45 }46 47 int main()48 {49 memset(Relation,-1,sizeof(Relation));50 for (int i=1; i<=15; ++i)51 if (i%2==(1^(i>=6 && i<=10)))52 {53 for (int j=1; j<=3; ++j)54 for (int k=1; k<=2; ++k)55 {56 char opt=getchar();57 while (opt!='>' && opt!='<') opt=getchar();58 if (opt=='>')59 {60 Relation[(j-1)*3+k+(i/2+(i>10))*9][(j-1)*3+k+(i/2+(i>10))*9+1]=1;61 Relation[(j-1)*3+k+(i/2+(i>10))*9+1][(j-1)*3+k+(i/2+(i>10))*9]=0;62 }63 else64 {65 Relation[(j-1)*3+k+(i/2+(i>10))*9+1][(j-1)*3+k+(i/2+(i>10))*9]=1;66 Relation[(j-1)*3+k+(i/2+(i>10))*9][(j-1)*3+k+(i/2+(i>10))*9+1]=0;67 }68 }69 70 }71 else72 {73 for (int j=1; j<=9; ++j)74 {75 char opt=getchar();76 while (opt!='^' && opt!='v') opt=getchar();77 if (opt=='v')78 {79 Relation[id(i/2+(i>=5),j)][id(i/2+(i>=5)+1,j)]=1;80 Relation[id(i/2+(i>=5)+1,j)][id(i/2+(i>=5),j)]=0;81 }82 else83 {84 Relation[id(i/2+(i>=5)+1,j)][id(i/2+(i>=5),j)]=1;85 Relation[id(i/2+(i>=5),j)][id(i/2+(i>=5)+1,j)]=0;86 }87 }88 }89 Dfs(1,1);90 }