「BZOJ3109」[CQOI2013] 新数独
Description
.jpg)
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
< > < > < >
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
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<iostream> #include<cstdio> #define searchnext(x,y) y==9? search(x+1,1):search(x,y+1) using namespace std; int ans[10][10]; int cpl[10][10],cpr[10][10]; bool usel[10][10],user[10][10],uses[10][10],flag; void print() { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { printf("%d",ans[i][j]); if(j!=9)printf(" "); } printf("\n"); } } int cmp(int x,int y){return x>y? 1:-1;} bool pd(int x,int y,int k) { if(usel[x][k]||user[y][k])return 0; if(uses[((x-1)/3)*3+(y-1)/3+1][k])return 0; if(cmp(k,ans[x][y-1])!=cpl[x][y]&&cpl[x][y]!=0)return 0; if(cmp(k,ans[x-1][y])!=cpr[x][y]&&cpr[x][y]!=0)return 0; usel[x][k]=user[y][k]=uses[((x-1)/3)*3+(y-1)/3+1][k]=1; return 1; } void search(int x,int y) { if(x==10) {flag=1;print();return;} if(flag)return; for(int i=1;i<=9;i++) { if(pd(x,y,i)) { ans[x][y]=i; searchnext(x,y); ans[x][y]=0; usel[x][i]=user[y][i]=uses[((x-1)/3)*3+(y-1)/3+1][i]=0; } } } int main() { char ch[2]; for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { if(j%3!=0) { scanf("%s",ch); if(ch[0]=='>')cpl[i][j+1]=-1; else cpl[i][j+1]=1; } } if(i%3!=0) for(int j=1;j<=9;j++) { scanf("%s",ch); if(ch[0]=='v')cpr[i+1][j]=-1; else cpr[i+1][j]=1; } } search(1,1); return 0; } |
Subscribe
计数器 9856788
OI 课件=>
OI 课件=>