深搜，广搜

在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 

待续……

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有