专题讲解--搜索例题（八皇后、骑士问题、母亲的牛奶）

1、八皇后问题

一个如下的  6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。


上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i个数字表示在第 i 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入格式
一行一个正整数 n，表示棋盘是 n×n大小的。

输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数

拿到这道题的第一个想法就是dfs。因为我们要保证每个皇后不在同一个对角线，不在一行，不在一列。所以我们每次把第k个皇后放在第k行，即保证每个皇后都不在同一行。接下来我们要判断每个皇后是否在一列或者对角线即可。我们设一个queen数组表示每个皇后所放位置所在列prey == ny || prey-prex == ny-nx || prey + prex == ny + nx。如果以上条件都不成立，那么皇后k的放置就是合理的。把当前合理的位置记录下来，以便下次遍历。

代码如下（由于代码比较卡，所以加了很多register又开了O2才过）：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 int n;
 8 bool vis[10];
 9 int a[10];
10 int queen[100];
11 bool flag;
12 int ans=0;
13 inline int read()
14 {
15     int x = 1,a = 0;
16     char ch = getchar();
17     while(ch < '0' || ch > '9'){
18         if(ch == '-')x = -1;
19         ch = getchar();
20     }
21     while(ch <= '9'&&ch >= '0'){
22         a = a * 10 + ch - '0';
23         ch = getchar();
24     }
25     return x*a;
26 }
27 inline void dfs(int k)
28 {
29     if (k>n){
30         ans++;
31         if (ans<=3){
32             for (register int i = 1;i <= n;i++){
33                 printf ("%d ",queen[i]);
34             }
35             printf ("
");
36         }
37     }
38     for (register int i = 1;i <= n;i++){
39     
40         int x = k,y = i;
41         flag=true;
42         for (register int j = 1;j < k&&flag;j++){
43             int prex = j,prey = queen[j];
44             if (y==prey||prey+prex==y+x||prex-prey==x-y)
45                 flag = false;
46             
47         }
48         if (flag){
49             queen[k] = y;
50             dfs(k+1);
51         }
52     }
53 }
54 int main()
55 {
56     n=read();
57     dfs(1);
58     printf ("%d
",ans);
59     return 0;
60 }

题意翻译

输入8*8的国际象棋棋盘上的2个格子（列：a~h，行：1~8），求马至少多少步从起点（键盘输入的第一个位置）跳到终点（键盘输入的第二个位置）。

一个双向bfs的题解，好像还可以过八数码难题的说

题意：

给定起始状态和结束状态，以及状态转换的规则，求最少的状态转换次数
解决：

一般情况下，BFS 第一次遇到末状态时的深度即为“最少次数”，所以使用 BFS 求解
优化：

一般的 BFS 通常是从某一状态开始搜索，某节点第一次达到结束状态时停止，属于“单向”搜索（单调向某一方向拓展）

但在本题中给出了固定的起始状态和结束状态，这时可以使用 “ 双向BFS ” 进行优化，顾名思义——即从两个状态开始搜索，这时当两个搜索树第一次出现节点重合就得到了 “ 最少次数 ” 。
解释：

① 搜索的停止：从起始状态和结束状态拓展出来的搜索树第一次出现节点重合时，起始点和结束点之间就有一条路径相连接，即求得解。

② 起到优化作用的原因：如果把 BFS 搜索树都看成一棵二叉树，那么高度为h的二叉树至多有 $2^h-1个节点$

代码实现：

　　通常使用两个队列分别储存从两个状态开始的搜索状态，用vis数组判断是否重合，用dis数组储存每个节点的深度，遇到解的时候直接调用dis数组以输出。

　　而搜索方式一般是：每次都选择节点个数少的那个队列拓展

　　方位数组，表示骑士能走的八个方向。

　　用两个数组vis1和vis2来记录分别从初位置和末位置所走到的点为1和2，判重的时候，只需要判断是否从初位置走的点碰到2或者从末位置走的点碰到了1。

　　终于弄懂啦，代码如下！

 1 #include<queue>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=10;
 6 char a[N],b[N];
 7 int dx[N]={-1,-2,-2,-1,1,2,2,1};
 8 int dy[N]={-2,-1,1,2,2,1,-1,-2};
 9 struct node{
10     int x,y,t;
11 }st,ed,tmp;
12 int dis[N][N],vis[N][N];
13 int bfs()
14 {
15     if(st.x==ed.x&&st.y==ed.y) return 0;
16     queue<node> q1;
17     queue<node> q2;
18     vis[st.x][st.y]=1;
19     vis[ed.x][ed.y]=2;
20     q1.push(st);
21     q2.push(ed);
22     int fx,fy,xx,yy;
23     while(true){
24         if(q1.size()<q2.size()){
25             fx=q1.front().x;
26             fy=q1.front().y;
27             for(int i=0;i<8;i++){
28                 xx=fx+dx[i];yy=fy+dy[i];
29                 if(xx<1||xx>8||yy<1||yy>8) continue;
30                 if(vis[xx][yy]==0){
31                     tmp.t=q1.front().t+1;
32                     tmp.x=xx;tmp.y=yy;
33                     q1.push(tmp);
34                     vis[xx][yy]=1;
35                     dis[xx][yy]=tmp.t;
36                 }
37                 else if(vis[xx][yy]==2)
38                 return dis[xx][yy]+q1.front().t+1;
39             }q1.pop();
40         }
41         else{
42             fx=q2.front().x;
43             fy=q2.front().y;
44             for(int i=0;i<8;i++){
45                 xx=fx+dx[i];yy=fy+dy[i];
46                 if(xx<1||xx>8||yy<1||yy>8) continue;
47                 if(vis[xx][yy]==0){
48                     tmp.t=q2.front().t+1;
49                     tmp.x=xx;tmp.y=yy;
50                     q2.push(tmp);
51                     vis[xx][yy]=2;
52                     dis[xx][yy]=tmp.t;
53                 }
54                 else if(vis[xx][yy]==1)
55                 return dis[xx][yy]+q2.front().t+1;
56             }q2.pop();
57         }
58     }
59 }
60 int main(void)
61 {
62     while(scanf("%s%s",a,b)!=EOF){
63         st.x=a[0]-'a'+1;st.y=a[1]-'0';
64         ed.x=b[0]-'a'+1;ed.y=b[1]-'0';
65         st.t=ed.t=0;
66         memset(vis,0,sizeof(vis));
67         memset(dis,0,sizeof(dis));
68         printf("To get from %c%c to %c%c takes %d knight moves.
",a[0],a[1],b[0],b[1],bfs());
69     }
70     return 0;
71 }

3.母亲的牛奶

题目描述

农民约翰有三个容量分别是

最初，

当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当

输入格式

单独的一行包括三个整数

输出格式

只有一行，升序地列出当

$一共可以分六种情况：但是每一种情况有一个前提就是得到水的桶并没有装满$

$就拿其中的一种情况来说 a给b a剩余的水为va-(min(b,va+vb)-vb)如果b可容纳的比a原本的多，a就为空，反之，a剩水。va+vbmin(b,va+vb)对b来说如果b所能容纳的比a少，b就满了，反之b剩余vc，c中的水不变$

$对于其他五种情况a给c，b给a，b给c，c给a，c给b都是一样的$

$代码如下：$

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int a,b,c;
 7 bool vis[25][25][25];
 8 int k=0;int ans[100];
 9 void dfs(int va,int vb,int vc)
10 {
11     if (vis[va][vb][vc])return;
12     if (va==0) 
13     {
14         k++;
15         ans[k]=vc;
16     }
17     vis[va][vb][vc]=1;
18      if(vc){
19         if(va<a)
20         dfs(min(a,va+vc),vb,vc-(min(a,va+vc)-va));
21         if(vb<b)
22         dfs(va,min(vb+vc,b),vc-(min(b,vb+vc)-vb));
23     }
24     if(vb){
25         if(va<a)
26         dfs(min(a,va+vb),vb-(min(a,va+vb)-va),vc);
27         if(vc<c)
28         dfs(va,vb-(min(c,vc+vb)-vc),min(c,vc+vb));
29     }
30     if(va){
31         if(vb<b)
32         dfs(va-(min(b,va+vb)-vb),min(b,va+vb),vc);
33         if(vc<c)
34         dfs(va-(min(c,va+vc)-vc),vb,min(c,vc+va));
35     }
36     return;
37 }
38 int main()
39 {
40     scanf ("%d%d%d",&a,&b,&c);
41     dfs(0,0,c);    
42     sort(ans+1,ans+k+1);
43     for(int i=1;i<=k;i++)printf("%d ",ans[i]);
44     return 0;
45 }