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;
}
           

這就是對深度搜尋和廣度搜尋的簡單講解，學的時間并不長，如有不足，歡迎指正。