UVa 750

　　题目大意：八皇后问题，在一个8*8的棋盘上，放置8个皇后，使得任意两个皇后不在同一行上、不在同一列上、不在同一条对角线上，不过这道题预先给定了一个位置放置一个皇后，让你输出所有可能的答案。

　　经典的回溯问题，具体可参考《算法竞赛入门经典》7.4.1，不过这道题对输出的要求说的挺模糊的，要特别注意输出的格式。开始不知道，就WA了一次...

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 8
 4 
 5 bool vis[3][2*N];
 6 int r, c, kase;
 7 int ans[N];
 8 
 9 void search(int cur)
10 {
11     if (cur == N)
12     {
13         printf("%2d      ", ++kase);
14         for (int i = 0; i < N; i++)
15             printf("%d%s", ans[i]+1, (i==N-1) ? "
" : " ");
16         return;
17     }
18     if (cur == c)  search(cur+1);
19     else
20     {
21         for (int i = 0; i < N; i++)
22             if (!vis[0][i] && !vis[1][cur-i+N] && !vis[2][cur+i])
23             {
24                 ans[cur] = i;
25                 vis[0][i] = vis[1][cur-i+N] = vis[2][cur+i] = 1;
26                 search(cur+1);
27                 vis[0][i] = vis[1][cur-i+N] = vis[2][cur+i] = 0;
28             }
29     }
30 }
31 
32 int main()
33 {
34 #ifdef LOCAL
35     freopen("in", "r", stdin);
36 #endif
37     int T;
38     scanf("%d", &T);
39     while (T--)
40     {
41         scanf("%d%d", &r, &c);
42         r--;
43         c--;
44         memset(vis, 0, sizeof(vis));
45         vis[0][r] = 1;
46         vis[1][c-r+N] = 1;
47         vis[2][c+r] = 1;
48         ans[c] = r;
49         kase = 0;
50         printf("SOLN       COLUMN
");
51         printf(" #      1 2 3 4 5 6 7 8

");
52         search(0);
53         if (T)  printf("
");
54     }
55     return 0;
56 }

View Code

　　为了提高时间，可以预先打表，貌似只有92种方案，然后从中选择就可以了。