真的naive......
我把所有能剪的枝都剪了才过的。否则就是TTT
还有个很神奇的事：数组作为参数传进递归函数时会造成上一层函数里的数组的改变。这个我TM调了一天。
下面奉上代码
1 #include <cstdio>
2 #include <cstring>
3 using namespace std;
4
5 int a[5][5];
6 int xx,yy;
7
8
9 void dfs(bool b[],int x,int y)
10 {
11 if(y>4) x++,y=1;
12 /* printf("%d %d
",x,y);
13 for(int i=1;i<=4;i++)
14 {
15 for(int j=1;j<=4;j++) printf("%d ",a[i][j]);
16 printf("
");
17 }
18 for(int i=0;i<=3;i++)
19 {
20 for(int j=1;j<=4;j++) printf("%d ",b[i*4+j]);
21 printf("
");
22 }
23 printf("
");
24 */
25 if(x==3&&y==4)
26 {
27 a[3][4]=34-a[3][1]-a[3][2]-a[3][3];
28 if(a[3][4]>16||a[3][4]<1) {return;}
29
30 if(b[a[3][4]]) {return;}
31
32 b[a[3][4]]=1;
33
34 for(int i=1;i<=4;i++)
35 {
36 a[4][i]=34-a[1][i]-a[2][i]-a[3][i];
37 if(a[4][i]>16||a[4][i]<1)
38 {
39 for(int j=1;j<i;j++) b[a[4][j]]=0;
40 b[a[3][4]]=0;
41 return;
42 }
43 if(b[a[4][i]])
44 {
45 for(int j=1;j<i;j++) b[a[4][j]]=0;
46 b[a[3][4]]=0;
47 return;
48 }
49 b[a[4][i]]=1;
50 }
51 ///b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;
52 if(a[xx][yy]!=1) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
53 if(a[4][1]+a[4][2]+a[4][3]+a[4][4]!=34) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
54 if(a[3][1]+a[3][2]+a[4][1]+a[4][2]!=34) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
55 if(a[3][3]+a[3][4]+a[4][3]+a[4][4]!=34) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
56 if(a[1][1]+a[2][2]+a[3][3]+a[4][4]!=34) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
57 if(a[1][4]+a[2][3]+a[3][2]+a[4][1]!=34) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
58 for(int i=1;i<=16;i++) if(b[i]!=1) {b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;return;}
59 for(int i=1;i<=4;i++)
60 {
61 for(int j=1;j<=4;j++) printf("%d ",a[i][j]);
62 printf("
");
63 }
64 printf("
");
65 b[a[4][1]]=0;b[a[4][2]]=0;b[a[4][3]]=0;b[a[4][4]]=0;b[a[3][4]]=0;
66 return;
67 }
68 if(y==4)
69 {
70 a[x][y]=34-a[x][1]-a[x][2]-a[x][3];
71 if(x==xx&&y==yy&&a[x][y]!=1) return;
72 //printf("%d=34-%d-%d-%d
",a[x][4],a[x][1],a[x][2],a[x][3]);
73 if(a[x][y]>16||a[x][y]<1) {a[x][y]=0;return;}
74 if(b[a[x][y]]) {a[x][y]=0;return;}
75 if(x==2) if(a[1][3]+a[1][4]+a[2][3]+a[2][4]!=34) {a[x][y]=0;return;}
76 b[a[x][y]]=1;
77 dfs(b,x,y+1);
78 b[a[x][y]]=0;
79 a[x][y]=0;
80 return;
81 }
82 if(x==2&&y==2)
83 {
84 a[x][y]=34-a[1][1]-a[1][2]-a[2][1];
85 if(x==xx&&y==yy&&a[x][y]!=1) return;
86 if(a[x][y]>16||a[x][y]<1) {a[x][y]=0;return;}
87 if(b[a[x][y]]) {a[x][y]=0;return;}
88 b[a[x][y]]=1;
89 dfs(b,x,y+1);
90 b[a[x][y]]=0;
91 a[x][y]=0;
92 return;
93 }
94 if(x==xx&&y==yy)
95 {
96 a[x][y]=1;
97 if(b[1]) return;
98 b[1]=1;
99 dfs(b,x,y+1);
100 a[x][y]=0;
101 b[1]=0;
102 return;
103 }
104 for(int i=2;i<=16;i++)
105 {
106 if(b[i]) continue;
107 a[x][y]=i;
108 b[i]=1;
109
110 dfs(b,x,y+1);
111 a[x][y]=0;
112 b[i]=0;
113 }
114 return;
115 }
116
117
118 int main()
119 {
120 scanf("%d%d",&xx,&yy);
121 bool b[34];
122
123 memset(b,0,sizeof(b));
124 dfs(b,1,1);
125 return 0;
126 }
最近开始重温寒假精英班的课程，从打好搜索开始重新打基~~础~~！