2010年1月9日星期六.sgu125
sgu125:搜
题意还是很好理解的，给出一个N*N的矩阵,B[i][j]表示周围有多少个元素比他大，每个元素的取值范围是1-9,最大的复杂度是9^9次方，大约需要5s才能跑出来，肯定需要优化。
由于题目中的限制很多，非常容易想到判断当前B的合法性来判断。
仔细想想，加上一个或者两个剪枝就可以了。
贴个超级丑陋的代码。。。。 这个题的代码写的确实不太好
1 /*
2 * SOUR:sgu125
3 * ALGO:dfs
4 * DATE: 2010年 01月 08日 星期五 22:46:13 CST
5 * COMM:3 http://www.cppblog.com/schindlerlee/
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 typedef long long LL;
14 const int maxint = 0x7fffffff;
15 const long long max64 = 0x7fffffffffffffffll;
16 const int N = 8;
17 int A[N][N];
18 int B[N][N],n;
19 int S[N][N];
20
21 #define PUSH(x,y) (S[x][y]++)
22 #define POP(x,y) (S[x][y]--)
23 #define legal(x,y) (S[x][y] <= B[x][y])
24
25 bool dfs(int x, int y)
26 {
27 if (y == n + 1) {
28 x++, y = 1;
29 }
30
31 if (x == n + 1) {
32 for(int i = 1;i <= n;i++) {
33 for(int j = 1;j <= n;j++) {
34 if(S[i][j] != B[i][j]) return false;
35 }
36 }
37 return true;
38 }
39 if(x == 3 && y == 1) {
40 if(S[1][1] != B[1][1] ||
41 S[1][2] != B[1][2] ||
42 S[1][3] != B[1][3])
43 return false;
44 }
45
46 for (int i = 1; i <= 9; i++) {
47 A[x][y] = i;
48 if (x > 1 && A[x][y] > A[x - 1][y]) {
49 PUSH(x - 1, y);
50 if (y > 1 && A[x][y] > A[x][y - 1]) {
51 PUSH(x, y - 1);
52 if(legal(x-1,y) && legal(x,y-1) && dfs(x,y+1)) return true;
53 else {
54 POP(x-1,y);
55 POP(x,y-1);
56 }
57 } else if (y > 1 && A[x][y] < A[x][y - 1]) {
58 PUSH(x, y);
59 if(legal(x-1,y) && legal(x,y) && dfs(x,y+1)) return true;
60 else {
61 POP(x-1,y);
62 POP(x,y);
63 }
64 } else {
65 if(legal(x-1,y) && dfs(x,y+1)) return true;
66 else {
67 POP(x-1,y);
68 }
69 }
70 } else if (x > 1 && A[x][y] < A[x - 1][y]) {
71 PUSH(x, y);
72 if (y > 1 && A[x][y] > A[x][y - 1]) {
73 PUSH(x, y - 1);
74 if(legal(x,y) && legal(x,y-1) && dfs(x,y+1)) return true;
75 else {
76 POP(x,y);
77 POP(x,y-1);
78 }
79 } else if (y > 1 && A[x][y] < A[x][y - 1]) {
80 PUSH(x, y);
81 if(legal(x,y) && dfs(x,y+1)) return true;
82 else {
83 POP(x,y);
84 POP(x,y);
85 }
86 } else {
87 if(dfs(x,y+1)) return true;
88 else {
89 POP(x,y);
90 }
91 }
92 }else {
93 if (y > 1 && A[x][y] > A[x][y - 1]) {
94 PUSH(x, y - 1);
95 if(dfs(x,y+1)) return true;
96 else {
97 POP(x,y-1);
98 }
99 } else if (y > 1 && A[x][y] < A[x][y - 1]) {
100 PUSH(x, y);
101 if(dfs(x,y+1)) return true;
102 else {
103 POP(x,y);
104 }
105 } else {
106 if(dfs(x,y+1)) return true;
107 else {
108 }
109 }
110 }
111 }
112 return false;
113 }
114
115 int main()
116 {
117 int i, j, k;
118 scanf("%d", &n);
119 for (i = 1; i <= n; i++) {
120 for (j = 1; j <= n; j++) {
121 scanf("%d", &B[i][j]);
122 }
123 }
124
125 if (dfs(1, 1)) {
126 for(int i = 1;i <= n;i++) {
127 for(int j = 1;j <= n;j++) {
128 printf("%d ",A[i][j]);
129 }
130 putchar(10);
131 }
132 }else {
133 puts("NO SOLUTION");
134 }
135 return 0;
136 }
137