poj3083走玉米地问题

走玉米地迷宫，一般有两种简单策略，遇到岔路总是优先沿着自己的左手方向，或者右手方向走。给一个迷宫，给出这两种策略的步数，再给出最短路径的长度。

#########

#.#.#.#.#

S.......E

#.#.#.#.#

#########   迷宫示例
前两种策略用DFS的方法，最后一种用BFS的方法分别确定路线。易错点：
1.这道题目因为在走的时候遇到死路需要回头，且这个步数也要计算在内，所以不需要将走过的路设置标志。
2.总是沿着当前的左边或者右边走，即方向需要不断调整
贴代码如下：

 #include<iostream>

 #include<string>

 #include<queue>

 using namespace std;

 typedef class

 {

 public:

     int x,y;

     int path;

 }vertex;

 char maze[][];

 int trace[][];

 int lpath,rpath,spath;

 queue<vertex> bfq;

 int incre[][]={  //first LEFT, then MID, last RIGHT

     {-,,,,,,,-},

     {,,,,,-,-,},

     {,,,-,-,,,},

     {,-,-,,,,,}

 };

 int LDFS(int x,int y,int ind)

 {

     int nind;

     trace[x][y]=;

     if(maze[x][y]=='E')

     {

         cout<<lpath<<" ";

         return -;

     }

     //左转

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         lpath++;

         nind=(ind+)%;

         if(LDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     //直行

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         lpath++;

         if(LDFS(x+incre[ind][],y+incre[ind][],ind)==-) return -;

     }

     //右转

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         lpath++;

         nind=(ind+)%;

         if(LDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     //后转

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         lpath++;

         nind=(ind+)%;

         if(LDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     return lpath;

 }

 int RDFS(int x,int y,int ind)

 {

     int nind;

        trace[x][y]=;

     if(maze[x][y]=='E')

     {

         cout<<rpath<<" ";

         return -;

     }

     //右转

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         rpath++;

         nind=(ind+)%;

         if(RDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         rpath++;

         if(RDFS(x+incre[ind][],y+incre[ind][],ind)==-) return -;

     }

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         rpath++;

         nind=(ind+)%;

         if(RDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     if(maze[x+incre[ind][]][y+incre[ind][]]!='#'&&trace[x+incre[ind][]][y+incre[ind][]]==)

     {

         rpath++;

         nind=(ind+)%;

         if(RDFS(x+incre[ind][],y+incre[ind][],nind)==-) return -;

     }

     return rpath;

 }

 void BFS(vertex v,int ind)

 {

     vertex a,b;

     bfq.push(v);

     trace[v.x][v.y]=;

     while(bfq.size()!=)

     {

         a=bfq.front();

         bfq.pop();

         if(maze[a.x+incre[ind][]][a.y+incre[ind][]]!='#'&&trace[a.x+incre[ind][]][a.y+incre[ind][]]==)

         {

             trace[a.x+incre[ind][]][a.y+incre[ind][]]=;

             b.x=a.x+incre[ind][];   b.y=a.y+incre[ind][];   b.path=a.path+;

             if(maze[b.x][b.y]=='E')

             {

                 cout<<b.path<<endl;

                 break;

             }

             bfq.push(b);

         }

         if(maze[a.x+incre[ind][]][a.y+incre[ind][]]!='#'&&trace[a.x+incre[ind][]][a.y+incre[ind][]]==)

         {

             trace[a.x+incre[ind][]][a.y+incre[ind][]]=;

             b.x=a.x+incre[ind][];   b.y=a.y+incre[ind][];   b.path=a.path+;

             if(maze[b.x][b.y]=='E')

             {

                 cout<<b.path<<endl;

                 break;

             }

             bfq.push(b);

         }

         if(maze[a.x+incre[ind][]][a.y+incre[ind][]]!='#'&&trace[a.x+incre[ind][]][a.y+incre[ind][]]==)

         {

             trace[a.x+incre[ind][]][a.y+incre[ind][]]=;

             b.x=a.x+incre[ind][];   b.y=a.y+incre[ind][];   b.path=a.path+;

             if(maze[b.x][b.y]=='E')

             {

                 cout<<b.path<<endl;

                 break;

             }

             bfq.push(b);

         }

         if(maze[a.x+incre[ind][]][a.y+incre[ind][]]!='#'&&trace[a.x+incre[ind][]][a.y+incre[ind][]]==)

         {

             trace[a.x+incre[ind][]][a.y+incre[ind][]]=;

             b.x=a.x+incre[ind][];   b.y=a.y+incre[ind][];   b.path=a.path+;

             if(maze[b.x][b.y]=='E')

             {

                 cout<<b.path<<endl;

                 break;

             }

             bfq.push(b);

         }

     }

 }

 int main()

 {

     int instan,w,h,i,j,sx,sy,ind;

     char in;

     cin>>instan;

     for(int Num=;Num<instan;Num++)

     {

         cin>>w>>h;

         for(i=;i<h;i++)

             for(j=;j<w;j++)

             {

                 cin>>in;

                 maze[i][j]=in;

                 if(maze[i][j]=='S')

                 {

                     sx=i;sy=j;

                 }

             }

         if(sy==) ind=;

         if(sx==) ind=;

         if(sy==(w-)) ind=;

         if(sx==(h-)) ind=;

         lpath=;

         memset(trace,,sizeof(trace));

         lpath=LDFS(sx,sy,ind);

         rpath=,spath=;

         memset(trace,,sizeof(trace));

         rpath=RDFS(sx,sy,ind);

         //cout<<lpath<<" "<<rpath<<endl;

         vertex vs;

         vs.x=sx;vs.y=sy;vs.path=;

         memset(trace,,sizeof(trace));

         BFS(vs,ind);

         while(bfq.empty()!=)

         {

             bfq.pop();

         }

     }

     return ;

 }