深搜，廣搜，深搜和廣搜

深搜，廣搜，深搜和廣搜

在acm課上聽陳宇講過幾個搜索題，當時就是照貓畫虎，按照他給的代碼改改就能過，那個代碼比較巧，好記的：

  int dfs(int i,int j)

{ if(i<0||i>=n||j<0||j>=m||map[i][j]=='#||v[i][j]==1)  //越界或搜索過退出

    return 0;

   v[i][j]=1;    

return 1+dfs(i,j+1)+dfs(i,j-1)+dfs(i-1,j)+dfs(i+1,j);  計算搜索過的數

這個函數就可以進行搜索n*m大的一個圖，或者說經常是迷宮搜索。

上面的其實就是廣搜，也叫寬搜，使用遞歸方式，然而有時候數據量過大時有可能會棧溢出，因此，正宗的廣搜使用遞推寫的，隊列加數組，其實原理就是把需要搜索的四個方向的點都加入隊列中，然後循環條件為隊列非空，再加個標記數組判重就好了。

 que.push(x1,y1);

 memset(vis,0,sizeof(vis));

 vis[x1][y1]=1;

while(!que.empty())

{   p tmp=que.front();

    que.pop();

  for(int i=0;i<4;i++)

 {  int ti=movex[i]+tmp.x,tj=movey[i]+tmp.y;

    if(ti>=1&&ti<=n&&tj>=1&&tj<=m&&map[ti][tj]=='*'&&!vis[ti][tj])

    {     que.push(ti,tj);

          vis[ti][tj]=1; }

  }       }

求最短路的話，就是再加一個結構體數組存放原圖，坐標和步數，然後點a向四個方向擴散時步數都是加1，這樣就是最短路了。

練習題d就是最短路了：http://acm.hust.edu.cn/vjudge/contest/127342#problem/D

代碼，看看那個結構體的應用就好了，這題的預處理和其他處理比較麻煩。

#include<iostream>

#include <cstring>

#include <queue>

#include <algorithm>

#include <cstdio>

using namespace std;

char map[21][21];

int vis[21][21];

int dir[4][2]={0,1,0,-1,1,0,-1,0};

int n,ans;

struct bu

{   int x,y;

   int cout;

   char c;

} b[500];

int cha(bus,char c)

{  if(vis[s.x][s.y]==0&&s.x>=0&&s.x<n&&s.y>=0&&s.y<n&&(s.c=='.'||(s.c<=c&&s.c>='A'&&s.c<='Z')))

return 1;

return 0;

}

void bfs(bu s,char c)

{    

queue <bu>q;

bu now,next;

s.cout=0;

q.push(s);

vis[s.x][s.y]=1;

while(!q.empty())

{    now=q.front();

      q.pop();

     if(now.c==c)

    {    ans++;

       res+=now.cout;

      map[now.x][now.y]='.';

       now.cout=0;

        mext.cout=0;

        memset(vis,0,sizeof(vis));

        return ;

      }

     for(int i=0;i<4;i++)

   {next.x=now.x+dir[i][0];

    next.y=now.y+dir[i][1];

    next.cout=now.cout+1;

   next.c=map[next.x][next.y];

   if(cha(next,c))

   q.push(next);

    }

}    

 return ; }

char a[1000];

int main()

{  int t;

  scanf("%d",&t);

ggetchar();

gets(a);

int tmp[26];

for(int ii=1;ii<=t;ii++)

{    memset(vis,0,sizeof(vis));

   res=0;

   ans=0;

   scanf("%d",&n);

  int k=0;

int l=0;

  for(int i=0;i<n;i++)

  cin>>map[i];

 for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

{   b[l].c=map[i][j];

    b[l].x=i;

    b[l].j=j;

if(b[l].c>='A'&&b[l].c<='Z)

{  k++;

  tmp[b[l].c-'A']=l;

}   

l++;

  }

for(int i=0;i<k;i++)

{  bfs(b[tmp[i-1]],'A'+i);

   if(ans<i)

   break;

}

if(ans==k-1&&k>0)

cout<<"Case"<<ii<<":"<<res<<endl;

else

cout<<"Case"<<ii<<":"<<"Impossible"<<endl;

}

}

深搜的話，從它的功能來說就是走出去可以退回來，有後悔路可走，每走一步可以先試試這步能不能走到底，模板的話，我就是把一開始的那個加以改造，應該比較簡單：

#include<iostream>

#include<string>

using namespace std;

struct ss

{  

int x,y;

}s[30];

int vis[30][30];

int n,m;

int dir[8][2]={-1,-2, 1,-2, -2,-1, 2,-1, -2,1, 2,1, -1,2, 1,2};   /八個方向         

int dfs(int i,int j,int q)

{   vis[i][j]=1;

  s[0].x=q;  記錄步數

  s[q].x=i,s[q].y=j; 記錄坐標

if（q==n*m)  走這麼多步後停止

retun 1;

int ii=i,jj=j;

for(int k=0;k<8;k++)

{  

ii=i+dir[k][1];

jj=j+dir[k][0];

if(!vis[ii][jj]&&ii>0&&ii<=n&&jj>0&&jj<=m)   判斷這步越界否

if(dfs(ii,jj,q+1)    判斷下一步能不能走通

return 1;

}

vis[i][j]=0;    走不通的話，程序就運行到這裡，標記數組還原為0

return 0;

}

練習題網址為   ：http://acm.hust.edu.cn/vjudge/contest/127342#problem/E
密碼為nefu 

待續……