bfs和dfs的简单使用
广度搜索和深度搜索的简单使用
小编我也是一个星期前才学的延迟搜索，当时学习的时候也是十分懵逼啊。
但是随着我深入的学习，终于是看出了一点的门道。
简单来说
dfs就是递归，bfs就是排队
接下来我会以题目和代码的形式来解释。
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
…#
…#.
.#…
#…
-1 -1
Sample Output
2
1
这道题就是dfs非常经典的棋盘问题了，当然它在八皇后问题的基础上还加了一些限制条件。
主要思路先提前将棋盘存入数组中，然后对每行进行遍历，遍历的过程中要注意将已经放下的棋子那一列进行标记，这样在之后的遍历中这一列就不能放旗子了。另外这题与八皇后问题最大的不同在于它给定了棋子的数目但并没有要求每行都有棋子，因此在递归的过程中要以棋子的数目当做递归的条件。下面附上代码。
#include<stdio.h>
#include<string.h>
int arr=0;
char maze[8][8];//定义棋盘
int used[8];//标记列
int n;
void f(int h,int k)//dfs
{
int i;
if(k==0)//当棋子摆完，结束遍历
{
arr++;
return;
}
if(h>=n)
return;//如果行数超过棋盘行数返回
for(i=0;i<n;i++)
{
if(used[i]==0&&maze[h][i]=='#')//遍历
{
used[i]=1;//将这一列标记
f(h+1,k-1);//对下一行进行遍历
used[i]=0;//取消标记
}
}
f(h+1,k);//无论这一行有没有摆放，都开始下一行的遍历
}
int main (void)
{
int k,i,j;
while(~scanf("%d %d",&n,&k)&&(n!=-1&&k!=-1))
{
memset(maze,0,sizeof(maze));//清空数组
memset(used,0,sizeof(used));
arr=0;
getchar();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%c",&maze[i][j]);//定义棋盘
}
getchar();
}
f(0,k);
printf("%d\n",arr);//输出个数
}
return 0;
}
看到这里想必你对dfs已经有一定了解了，然而dfs的缺点也是显而易见的，这就是一个一条路走到黑的方法，在寻找最优解上并不太适用，所以bfs就很好的解决了这个问题。
接下来我们还是以题目和代码的形式说明。
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N ( 0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers:
N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
这道题是英文形式，大致的意思就你站在N坐标要去抓一个坐标在K的牛，而你每分钟的行动有三种选择，从X的地方到X+1，X-1或2*X，假设这头牛不会动，问你最快抓到牛的时间。
这道题如果用dfs也可以解决，但一是不太容易找到最优解，二是复杂度太高了
所以这题我们用bfs解决，之前已经说明了，bfs说白了就是排队，将每一步的所有可能性放入队列中，再往后推，直到到达目标为止。
所以这题的思路也非常明确：
将每一分钟所做的所有行动排入队列中，直到抓到牛为止，接下来附上代码。
#include<stdio.h>
#include<string.h>
struct note//定义坐标和步数
{
int x;
int s;
};
int main (void)
{
int x1,x2,tx;
int head,tail;//定义头和尾
int i;
int used[100005];
int flag=0;
int sum=0;
struct note que[100005];//定义队列
memset(used,0,sizeof(used));
scanf("%d %d",&x1,&x2);
head=1;//将队首队尾都设置为1
tail=1;
que[head].x=x1;//将初始坐标存入队首
que[head].s=0;//将步数定为0
tail++;//队尾向后推
while(head<tail)
{
if(que[head].x==x2)//当到达目标点，停止排队
break;
for(i=1; i<=3; i++)//分别列出三种可能的行动方式
{
if(i==1)
tx=que[head].x+1;
else if(i==2)
tx=que[head].x-1;
else
tx=que[head].x*2;
if(tx<0||tx>100000)//走出所给定范围则不存入队列
continue;
if(used[tx]==0)
{
used[tx]=1;//对走过的点进行标记，避免重复
que[tail].x=tx;//将可能的坐标存入队尾
que[tail].s=que[head].s+1;//步数是队首所存的步数+1
tail++;队尾后推
}
if(tx==x2)//到达目标，退出循环
{
flag=1;//利用flag退出两层循环
break;
}
}
if(flag==1)
break;
head++;
}
printf("%d\n",que[tail-1].s);//由于最后队尾又后推一格，所以应该是队尾的前一格的步数。
return 0;
}
这就是对深度搜索和广度搜索的简单讲解，学的时间并不长，如有不足，欢迎指正。
