poj 3083 Children of the Candy Corn（DFS+BFS）

做了1天，总是各种错误，很无语
最后还是参考大神的方法
题意：从s到e找分别按照左侧优先和右侧优先的最短路径，和实际的最短路径
DFS找左右侧的最短路径
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<stack>
  6 #include<queue>
  7 #include<cmath>
  8 #include<algorithm>
  9 using namespace std;
 10 char G[50][50];
 11 int vis[50][50];
 12 int c,r;
 13 struct node
 14 {
 15     int x,y,dis;
 16 }s,pos,next;
 17 
 18 int dx[5]= {0,-1,0,1};
 19 int dy[5]= {-1,0,1,0};
 20 int dfs(int x,int y,int f,char ch)//这题dfs是重点，f表示当前的朝向
 21 {
 22     int i,j,nx,ny,nf;
 23     if(G[x][y]=='E')
 24         return 1;
 25     if(ch=='l')
 26     {
 27         for(i=f-1; i<f+3; i++)
 28         {
 29             nx=x+dx[(i+4)%4];
 30             ny=y+dy[(i+4)%4];
 31             nf=(i+4)%4;
 32             if(nx>=0&&nx<r&&ny>=0&&ny<c&&G[nx][ny]!='#')
 33                 return dfs(nx,ny,nf,ch)+1;
 34         }
 35     }
 36     else if(ch=='r')
 37     {
 38         for(i=f+1; i>f-3; i--)
 39         {
 40             nx=x+dx[(i+4)%4];
 41             ny=y+dy[(i+4)%4];
 42             nf=(i+4)%4;
 43             if(nx>=0&&nx<r&&ny>=0&&ny<c&&G[nx][ny]!='#')
 44                 return dfs(nx,ny,nf,ch)+1;
 45         }
 46     }
 47     return 0;
 48 }
 49 
 50 int bfs(int x,int y)
 51 {
 52     queue<node>q;
 53     int i;
 54     memset(vis,0,sizeof(vis));
 55     next.dis=1; next.x=x; next.y=y;
 56     vis[x][y]=1;
 57     q.push(next);
 58     while(!q.empty())
 59     {
 60        pos=q.front();
 61        q.pop();
 62        for(i=0; i<4; i++)
 63        {
 64            next.x=pos.x+dx[i]; next.y=pos.y+dy[i];
 65            next.dis=pos.dis+1;
 66            if(next.x>=0&&next.x<r&&next.y>=0&&next.y<c&&G[next.x][next.y]!='#'&&vis[next.x][next.y]==0)
 67            {
 68                q.push(next);
 69                vis[next.x][next.y]=1;
 70                 if(G[next.x][next.y]=='E')
 71                 return next.dis;
 72            }
 73        }
 74     }
 75     return 0;
 76 }
 77 int main()
 78 {
 79     int i,j,t;
 80     int le,ri,f,ans,flag;
 81     cin>>t;
 82     while(t--)
 83     {
 84         cin>>c>>r;
 85         for(i=0; i<r; i++)
 86             cin>>G[i];
 87         flag=0;
 88         for(i=0; i<r; i++)
 89         {
 90             for(j=0; j<c; j++)
 91                 if(G[i][j]=='S')
 92                 {
 93                     s.x=i;
 94                     s.y=j;
 95                     s.dis=1;
 96                     if(i==0)
 97                         f=3;
 98                     else if(i==r-1)
 99                         f=1;
100                     else if(j==0)
101                         f=2;
102                     else if(j==c-1)
103                         f=0;
104                     flag=1;
105                     break;
106                 }
107             if(flag)
108                 break;
109         }
110         le=dfs(s.x,s.y,f,'l');
111         ri=dfs(s.x,s.y,f,'r');
112         ans=bfs(s.x,s.y);
113         printf("%d %d %d
",le,ri,ans);
114     }
115     return 0;
116 }