程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 九度 題目1335:闖迷宮 題目1365:貝多芬第九交響曲

九度 題目1335:闖迷宮 題目1365:貝多芬第九交響曲

編輯:C++入門知識

九度 題目1335:闖迷宮 題目1365:貝多芬第九交響曲


 

 

 

簡單說說寬度優先搜索BFS

 

說實話,這是第一個自己寫的寬度優先搜索的題目,之前也是不太明白之間的區別,好吧,只能說自己學的太渣……

 

言歸正傳,對於初學者來說,可能最大的概念就是一個是深度搜索,一個是寬度搜索,好吧,我表示廢話了,我其實就是這個樣子的,然後一直不得甚解。。。所以第一次上來,我就直接搜索DFS,結果太明顯,就是TLE或者MLE,然後就抓狂中,這可能是很多初學者在開始的時候犯的錯誤了。

 

我個人的感覺寬度搜索和深度搜索都是很暴力的枚舉,但是區別呢,還是比較明顯的,就比如下面這兩題來說,基本上的都是一樣,通過題目的描述,都是最快找到,在深度優先搜索中就是要找到所有能到達的最短路徑了,所以,其實應該說都能夠找到的,只是花費的時間不一樣而已。

 

總結起來就是以下幾點:

1:寬度優先搜索的用意一般都會比較明顯,比如最小啊,就是有比較限制的時候,比較多的時候會用寬度優先,這個,可以用一個比喻來說,就是從一個點,滴墨水,看誰先到,這就是寬度,每做一步,墨水都會擴散,然後得到新的起始點,繼續擴散,一個循環的過程。

2:深度優先的話,用於枚舉多少類型的時候會比較多,很常見的應用就是8皇後,N皇後的問題了

 

附上兩題的題解

題目1365:貝多芬第九交響曲

題目鏈接地址http://ac.jobdu.com/problem.php?pid=1365

 

 

#include 
#include 
#include 
using namespace  std;
 
struct Node
{
    int x, y,step;
};
bool A[101][101];
short testCase[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
int Cal(int x,int y,int ex,int ey,int num)
{
    if(x==ex&&y==ey)
        return 0 ;
    queue  p;
    Node tmp,q;
    int result=0;
    tmp.x=x;
    tmp.y=y;
    tmp.step=0;
    p.push(tmp);
    while(p.size()>0)
    {
        tmp=p.front();
        p.pop();
        for (int i=0;i<8;i++)
        {
            q.x=tmp.x+testCase[i][0];
            q.y=tmp.y+testCase[i][1];
            if(q.x>0&&q.y<=num&&q.x<=num&&q.y>0&&!A[q.x][q.y])
            {
                q.step=tmp.step+1;
                A[q.x][q.y]=true;
                if(q.x==ex&&q.y==ey)
                    return q.step;
                else
                    p.push(q);
            }
        }
 
    }
    return -1;
}
 
int main()
{
    int num,x,y,ex,ey;
    //freopen(data.in,r,stdin);
    while(scanf(%d,&num)!=EOF)
    {
        memset(A,0,sizeof(A));
        scanf(%d%d%d%d,&x,&y,&ex,&ey);
        printf(%d
,Cal(x,y,ex,ey,num));
    }
    return 0;
}
/**************************************************************
    Problem: 1365
    User: vincent_ynh
    Language: C++
    Result: Accepted
    Time:450 ms
    Memory:1064 kb
****************************************************************/


 

九度 題目1335:闖迷宮

題目鏈接地址:http://ac.jobdu.com/problem.php?pid=1335

 

#include 
#include 
#include 
using namespace std;
//#define LOCAL
bool A[100][100];
struct Node
{
    int x,y,step;
};
 
int Cal(int num)
{
    if(num==1)
        return 0;
    Node first,second;
    first.x=0;
    first.y=0;
    first.step=0;
    int testCase[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    queue result;
    result.push(first);
    while(result.size()>0)
    {
        first=result.front();
        A[first.x][first.y]=true;
        result.pop();
        for (int i=0;i<4;i++)
        {
            second.x=first.x+testCase[i][0];
            second.y=first.y+testCase[i][1];
            second.step=first.step+1;
            if(second.x>=0&&second.y=0&&!A[second.x][second.y])
            {
                A[second.x][second.y]=true;
                if(second.x==num-1&&second.y==num-1)
                    return second.step;
                else
                    result.push(second);
            }
             
        }
    }
    return -1;
}
int main()
{
    int inf=10000;
#ifdef LOCAL
    freopen(data.in,r,stdin);
    freopen(data.out,w,stdout);
#endif
    int num;
    while(scanf(%d,&num)!=EOF)
    {
        for(int i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved