这次的题目叫图的深度&&广度优先遍历。

　　然后等我做完了题发现这是DFS&&BFS爆搜专题。

　　3278：题目是经典的FJ，他要抓奶牛。他和牛（只有一头）在一条数轴上，他们都站在一个点上（坐标为0~1e5）。假设FJ的位置为x，他每次可以去x+1,x-1,x*2的地方。问他最少走几次才能抓到他的牛（牛不会动）。

　　赤裸裸的BFS，注意判断是否越界（很容易RE）

　　CODE

#include
     
      #include
      
       using namespace std;const int N=100000;int q[N*3+10],step[N+5],n,k;bool vis[N+5];inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}int main(){    read(n); read(k);    memset(vis,true,sizeof(vis));    if (n>=k) printf("%d",n-k); else    {        int head=0,tail=1;        q[1]=n; step[n]=0; vis[n]=0;        while (head
       
        =0) if (vis[now-1]) vis[now-1]=0,q[++tail]=now-1,step[now-1]=step[now]+1;            if (now*2<=N) if (vis[now*2]) vis[now*2]=0,q[++tail]=now*2,step[now*2]=step[now]+1;        }    }    return 0;}
       
      
     

 

　　2049：一道迷宫BFS，和今年NOIP PJ T3 有点类似。题意可以百度翻译（这道题翻译的还是很好的，至少能看懂）

　　因为他给出的是网格的边而不是点，所以要进行转化。

　　我们用a[x][y][0]表示（x，y）右方向的边的属性（墙或门或空地），a[x][y][1]表示（x，y）上方向的边的属性（同理）

　　建图玩了以后可以再连边跑SPFA或者直接松弛BFS（循环更新到每个点的的最小通过门数）

　　最后提醒那个人有可能不在迷宫里，就直接输出0

　　CODE

#include
     
      #include
      
       using namespace std;const int N=205,INF=1e9,fx[4]={
   0,1,-1,0},fy[4]={
   1,0,0,-1};int a[N][N][2],f[N][N],q[N*N*10+10][2],n,m,i,j,x,y,d,t;double s_x,s_y;inline void read(int &x){    x=0; char ch=getchar(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}int main(){    for (;;)    {        read(n); read(m);        if (n==-1&&m==-1) break;        for (i=0;i
       
        199||y>199||(!n&&!m)) { puts("0"); continue; }        int head=0,tail=1;        q[1][0]=x; q[1][1]=y; f[x][y]=0;        while (head
        
         200||yy>200) continue;                if (i==0)                {                    if (a[xx][yy][0]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];                    if (a[xx][yy][0]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;                }                 if (i==1)                {                    if (a[xx][yy][1]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];                    if (a[xx][yy][1]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;                }                if (i==2)                {                    if (a[x][y][1]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];                    if (a[x][y][1]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;                }                if (i==3)                {                    if (a[x][y][0]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];                    if (a[x][y][0]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;                }            }        }        if (f[0][0]==INF) puts("-1"); else printf("%d\n",f[0][0]);    }    return 0;}
        
       
      
     

 

　　3083：这是一道神坑题，完美的展示了爆搜的含义。

　　题意是一个图，S起点，E终点，.是空地，#是墙不能走。问从S到E左优先和右优先以及最短步数是多少。

　　DFS+BFS。BFS最短和简单，终点的DFS。

　　因为他要求遵循左右的性质，所以方向数组的定义就很玄学了

　　以左优先为例 如果现在的方向是↑，那么优先级就是←↑→↓，其他方向同理（能左转就左转，不能转就向右转再判断），右优先同理。

　　因此预处理一下坐标的顺序就很水了。

　　CODE

#include
     
      #include
      
       #include
       
        using namespace std;const int N=45,l[4][4]={    {
    3,0,1,2},    {
    0,1,2,3},    {
    1,2,3,0},    {
    2,3,0,1},},r[4][4]={    {
    1,0,3,2},    {
    2,1,0,3},    {
    3,2,1,0},    {
    0,3,2,1},},fx[4]={
   0,-1,0,1},fy[4]={-1,0,1,0};char a[N][N];int q[N*N*10+10][2],step[N][N],i,j,n,m,s_x,s_y,e_x,e_y,t,w,l_ans,r_ans,min_ans;bool vis[N][N],flag;inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}inline void l_DFS(int x,int y,int w,int s){    if (flag) return;    if (x==e_x&&y==e_y) { l_ans=s; flag=1; return; }    for (int i=0;i<4;++i)    {        int xx=x+fx[l[w][i]],yy=y+fy[l[w][i]];        if (xx<=0||yy<=0||xx>n||yy>m) continue;        if (a[xx][yy]=='#') continue;        l_DFS(xx,yy,l[w][i],s+1);    }}inline void r_DFS(int x,int y,int w,int s){    if (flag) return;    if (x==e_x&&y==e_y) { r_ans=s; flag=1; return; }    for (int i=0;i<4;++i)    {        int xx=x+fx[r[w][i]],yy=y+fy[r[w][i]];        if (xx<=0||yy<=0||xx>n||yy>m) continue;        if (a[xx][yy]=='#') continue;        r_DFS(xx,yy,r[w][i],s+1);    }}inline void BFS(int s_x,int s_y){    memset(step,0,sizeof(step));    memset(vis,true,sizeof(vis));    int head=0,tail=1;    q[1][0]=s_x; q[1][1]=s_y;  step[s_x][s_y]=1; vis[s_x][s_y]=0;    while (head
        
         n||yy>m) continue;            if (a[xx][yy]=='#'||!vis[xx][yy]) continue;            q[++tail][0]=xx; q[tail][1]=yy; step[xx][yy]=step[x][y]+1; vis[xx][yy]=0;        }    }}int main(){
        read(t);    while (t--)    {        read(m); read(n);        for (i=1;i<=n;++i)        for (j=1;j<=m;++j)        {            cin>>a[i][j];            if (a[i][j]=='S') s_x=i,s_y=j;            if (a[i][j]=='E') e_x=i,e_y=j;        }        if (s_x==1) w=3; if (s_x==n) w=1; if (s_y==1) w=2; if (s_y==m) w=0;        flag=0; l_DFS(s_x,s_y,w,1);         flag=0; r_DFS(s_x,s_y,w,1);         BFS(s_x,s_y);        printf("%d %d %d\n",l_ans,r_ans,min_ans);    }    return 0;}