bnu 4358 左手定则（搜索）

http://www.bnuoj.com/bnuoj/problem_show.php?pid=4358

【题意】：给定起始位置和方向和目的地，按照左转、前进、右转、后退的优先级递减，也就是说能左转就左转，不能则继续前进，。。。，能走到T的位置输出YES,不能则输出NO。。。

【题解】：

　　首先我们知道YES肯定就是走到了，若出现NO的情况，肯定是出现了死循环，这题主要考标记，什么时候表示已经进入了死循环呢？每个位置有一个方向，我们将这个位置第一次出现方向的时候标记下来，注意是第一次的方向噢，第二次经过的时候判断，是否方向相同，相同则表示出现了跟之前一样的状态，也就是说出现了循环。。。

【code】：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 char map[][];

 int cx[]={-,,,};

 int cy[]={,,,-};

 int dr[][];

 int n,m;

 int isCheck(int x,int y)

 {

     if(x>=&&x<n&&y>=&&y<m)    return ;

     return ;

 }

 int search(int sx,int sy,int d)

 {

     while()

     {

         if(map[sx][sy]=='T')    return ;

        // cout<<sx<<" "<<sy<<endl;

         if(dr[sx][sy]==-)

         {

             dr[sx][sy]=d;

         }

         else if(dr[sx][sy]==d)

         {

             return ;

         }

         int tx,ty;

         //如果左边是空位

         int d1 = (d+)%;

         tx = sx+cx[d1];

         ty = sy+cy[d1];

         if(isCheck(tx,ty)&&map[tx][ty]!='#')//可以左转

         {

             sx = tx;

             sy = ty;

             d = d1;

         }

         else if(isCheck(tx,ty)&&map[tx][ty]=='#') //不可以左转

         {

           //   int d2 = (d+1)%4;

              int tx2 = sx+cx[d];

              int ty2 = sy+cy[d];

              if(isCheck(tx2,ty2))

              {

                  if(map[tx2][ty2]=='#')//前方不能走

                  {

                      int d2 = (d+)%;

                      int tx3 = sx+cx[d2];

                      int ty3 = sy+cy[d2];

                      if(isCheck(tx3,ty3))

                      {

                          if(map[tx3][ty3]!='#')//右边可以走

                          {

                               sx = tx3;

                               sy = ty3;

                               d = d2;

                          }

                          else //右边不可以走，向后走

                          {

                              int d3 = (d+)%;

                              sx = sx+cx[d3];

                              sy = sy+cy[d3];

                              d=d3;

                          }

                      }

                  }

                  else//前方能走

                  {

                        sx = tx2;

                        sy = ty2;

                  }

              }

         }

     }

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         memset(dr,-,sizeof(dr));

         int i,j,flag=;

         for(i=;i<n;i++)    scanf("%s",map[i]);

         char dir[];

         scanf("%s",dir);

         int d;

         if(dir[]=='N') d=;

         else if(dir[]=='E')    d=;

         else if(dir[]=='S')    d=;

         else if(dir[]=='W')    d=;

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

         {

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

             {

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

                 {

                     flag = search(i,j,d);

                     break;

                 }

             }

         }

         if(flag)    puts("YES");

         else puts("NO");

     }

     return ;

 }

巴特西

bnu 4358 左手定则（搜索）

最新文章

热门文章

巴特西

bnu 4358 左手定则 （搜索）

最新文章

热门文章

bnu 4358 左手定则（搜索）