25号搜索的一些例子，。。Oil Deposits&&Red and Black&&Knight Moves&&Catch That Cow&&Tempter of the Bone

Oil Depositshttp://poj.org/problem?id=1562

一个简单又基础的搜索题目：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 char a[105][105];
 7 int s=0,i,j,x,y;“有多个函数，应把变量定义在外面”深搜
 8 void dfs(int i,int j)
 9 {
10     if(i<1||i>x||j<1||j>y||a[i][j]!='@')
11         return ;//直接跳出来.
12         else
13     {a[i][j]='!';
14     dfs(i-1,j);
15     dfs(i-1,j-1);
16     dfs(i,j-1);
17     dfs(i,j+1);
18     dfs(i+1,j+1);
19     dfs(i-1,j+1);
20     dfs(i+1,j);
21     dfs(i+1,j-1);}
22 }
23 int main()
24 {
25     int i,j;
26     while(scanf("%d %d",&x,&y)!=EOF)
27     {
28         if(x==0||y==0)
29             break;
30             s=0;
31             for(i=1;i<=x;i++)
32                 for(j=1;j<=y;j++)
33                 cin>>a[i][j];。。。不能用scanf来输入(不清楚。)
34             for(i=1;i<=x;i++)
35                 for(j=1;j<=y;j++)
36                 {
37                     if(a[i][j]=='@')
38                     {
39                     dfs(i,j);
40                     s++;
41                     }
42                 }
43                 printf("%d
",s);
44     }
45     return 0;
46 }

Red and Blackhttp://poj.org/problem?id=1979

 1 #include<iostream>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<string.h>
 6 using namespace std ;
 7 char a[200][200];
 8 int x,y,s=0,i,j,n,m;
 9 void dfs(int i,int j)
10 {
11     if(i<1||i>y||j<1||j>x||a[i][j]!='.')
12         return ;
13     else
14     {
15         s++;
16         a[i][j]='@';
17         dfs(i+1,j);
18         dfs(i-1,j);
19         dfs(i,j+1);
20         dfs(i,j-1);
21     }
22  }
23 int main()
24 {
25     while(scanf("%d%d",&x,&y)!=EOF)
26     {
27         s=0;
28         if(x==0||y==0)
29             break;
30         for(i=1;i<=y;i++)
31         {
32                 scanf("%s",a[i]+1);
33         }//行列的转化，用字符串数组来进行输入
34             for(i=1;i<=y;i++)
35                 for(j=1;j<=x;j++)
36             {
37                 if(a[i][j]=='@')
38                 {
39                     a[i][j]='.';
40                     n=i;
41                     m=j;
42                     break;
43                 }
44             }
45             dfs(n,m);
46             printf("%d
",s);
47     }
48     return 0;
49 }

Knight Moveshttp://poj.org/problem?id=2243

前面三个题目都可以用bfs（）来计算，但前俩种有简便的方法。

思路：国际上的Knight Move是走”日子“形的（常识）。

这是最基础的模板！

 1 #include<iostream>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<string.h>
 6 using namespace std ;
 7 int sx,sy,ex,ey,map[10][10]；
 8 int dir[8][2]={{-2,-1}, {-2,1}, {-1,-2}, {-1, 2},{1,-2}, {1,2}, {2,-1}, {2,1}};//注意枚举来表示
 9 int bfs()//广搜要用到队列
10 {
11     int i,x1,y1,x2,y2;
12     memset(map,0,sizeof(map));
13     queue<int>Q ;
14     Q.push(sx);
15     Q.push(sy);
16     while(Q.empty()==0)
17     {
18         x1=Q.front();
19         Q.pop() ;
20         y1=Q.front();
21         Q.pop() ;
22         if(x1==ex && y1==ey)
23         {
24             return map[x1][y1];
25         }
26         for(i=0;i<8;i++)
27         {
28             x2=x1+dir[i][0];
29             y2=y1+dir[i][1];
30             if( x2>0 && x2<=8 && y2>0 && y2<=8 && map[x2][y2]==0)
31             {
32                 map[x2][y2]=map[x1][y1]+1;
33                 Q.push(x2);
34                 Q.push(y2);
35             }
36         }
37     }
38 }
39 int main()
40 {
41     while(scanf("%c%d %c%d%*c//什么情况",&sx,&sy,&ex,&ey)!=EOF)
42     {
43         sx=sx-'a'+1;
44         ex=ex-'a'+1;//变换
45         printf("To get from %c%d to %c%d takes %d knight moves.
",sx+'a'-1,sy,ex+'a'-1,ey,bfs());
46     }
47     return 0;
48 }

Catch That Cowhttp://poj.org/problem?id=3278

好像是最简单的一道搜索题，但仍有难度的！

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 int map1[200005];
 7 int a,b;
 8 int a1[4]={1,1,2},b1[4]={1,-1,0};
 9 int bfs()
10 {
11     int k,k1,i;
12     memset(map1,0,sizeof(map1));
13     queue<int> Q;
14     Q.push(a);
15     while(Q.empty()==0)
16     {
17         k=Q.front();
18         Q.pop();
19         if(k==b)
20         {
21             return map1[k];
22         }
23         for(i=0;i<3;i++)
24         {
25             k1=k*a1[i]+b1[i];
26             if(k1>=0&&k1<=200000&&map1[k1]==0)
27                 {
28                     map1[k1]=map1[k]+1;
29                     Q.push(k1);
30                 }
31         }
32 
33     }
34 }
35 int main()
36 {
37     while(scanf("%d %d",&a,&b)!=EOF)
38     printf("%d
",bfs());
39     return 0;
40 }

Tempter of the Bonehttp://acm.fafu.edu.cn/problem.php?id=1167

用Dfs（）来求解，首先要考虑不能到达的情况。。。

这题那个i不能乱定义！，所以变量的定义以及范围也要注意！

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 char a[7][7];
 7 int w[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 8 int x,y,t,n,m,n1,m1,flag;
 9 void dfs(int n,int m,int time)
10 {
11     int n2,m2,i;//变量的定义
12     if(n==n1&&m==m1&&time==t)
13         flag=1;
14     if(time>t)
15         return ;
16     if(flag)
17         return ;
18     if((t-time)%2!=(abs(n-n1)+abs(m-m1))%2)//奇偶剪枝（（t-time-abs(n-n1)-abs(m-m1)）%2!=0）
19         return ;
20     for(i=0;i<4;i++)
21     {
22         n2=n+w[i][0];
23         m2=m+w[i][1];
24         if(n2>=0&&n2<x&&m2>=0&&m2<y)
25         {
26             if(a[n2][m2]!='X')
27             {
28                 a[n2][m2]='X';
29                 dfs(n2,m2,time+1);
30                 a[n2][m2]='.';//回溯法
31             }
32 
33         }
34 
35     }
36 }
37 int main()
38 {
39     int k,i,j;//变量的定义
40     while(scanf("%d%d%d",&x,&y,&t)!=EOF)
41     {
42         k=0;
43         if(x==0&&y==0&&t==0)
44             break;
45         for(i=0;i<x;i++)
46             scanf("%s",a[i]);
47         for(i=0;i<x;i++)
48             for(j=0;j<y;j++)
49         {
50             if(a[i][j]=='S')
51             {
52                 n=i;
53                 m=j;
54                 a[i][j]='X';
55             }
56             if(a[i][j]=='D')
57             {
58                 n1=i;
59                 m1=j;
60                 k++;
61             }
62             if(a[i][j]=='.')
63                 k++;
64         }
65         if(k<t)
66         {
67             printf("NO
");
68             continue;
69         }
70         flag=0;
71         dfs(n,m,0);
72         if(flag)
73             printf("YES
");
74         else
75             printf("NO
");
76     }
77     return 0;
78 }

奇偶剪枝：

是数据结构的搜索中，剪枝的一种特殊小技巧。

现假设起点为(sx,sy)，终点为（ex,ey），给定t步恰好走到终点，

s
\|
\|
\|
+	—	—	—	e

如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；

s	—	—	—
	—	—	+
\|	+
\|
+	—	—	—	e

如图，为一般情况下非最短路径的任意走法举例，step2=14；

step2-step1=6，偏移路径为6，偶数（易证）；

故，若t-[abs(ex-sx)+abs(ey-sy)]结果为非偶数（奇数），则无法在t步恰好到达；

返回，false；

反之亦反。