题目链接：https://www.luogu.org/problemnew/show/P1126

思路：很不错的搜索题，用BFS，虐了我1天多才A掉 QAQ，细节很多。

　　　1.每个状态包含行、列、方向、步数。

　　　2.需要将格点图转换为点图。

　　　3.注意边界不能走。

　　　4.最后是折磨了大半天的，救赎最后输入的字符，我最开始是写的scanf("%d%d%d%d%c",&sr,&sc,&er,&ec,&d)。我一直在找算法部分的bug，怎么也没想到竟然是它没有读到输入的字符，而读的是空格。因为scanf虽然在读数据会吃掉空格和换行，但只有scanf读char时不会吃掉空格和换行，虽然以前碰到过一次，但还是没意识到啊...解决办法是在%c前加一个空格就行，吸取教训了，血的教训。

 

AC代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 struct cur{ 7     int r,c,dir,step; 8 }tmp; 9 queue
        
          q;10 int gr[4][3]={
   {-1,-2,-3},{
   0,0,0},{
   1,2,3},{
   0,0,0}};11 int gc[4][3]={
   {
   0,0,0},{
   1,2,3},{
   0,0,0},{-1,-2,-3}};12 int n,m,sr,sc,er,ec;13 int a[100][100];14 bool vis[100][100][5];15 16 void bfs(){17     q.push(tmp);18     while(!q.empty()){19         cur now=q.front();q.pop();20         int nr=now.r,nc=now.c,nd=now.dir,ns=now.step;21         if(nr==er&&nc==ec){22             printf("%d\n",ns);23             return;24         }25         for(int i=0;i<3;i++){26             int rr=nr+gr[nd][i],cc=nc+gc[nd][i];27             if(rr<=0||cc<=0||rr>=n||cc>=m||a[rr][cc])28                 break;29             if(!vis[rr][cc][nd]){30                 tmp.r=rr,tmp.c=cc,tmp.dir=nd,tmp.step=ns+1;31                 vis[rr][cc][nd]=true;32                 q.push(tmp);33             }34         }35         for(int i=-1;i<=1;i+=2){36             tmp.r=nr,tmp.c=nc;37             int dd=nd+i;38             if(dd==4)dd=0;39             if(dd==-1)dd=3;40             tmp.dir=dd;41             tmp.step=ns+1;42             if(!vis[nr][nc][dd]){43                 vis[nr][nc][dd]=true;44                 q.push(tmp);45             }    46         }    47     }48     printf("-1\n");49 }50 51 int main(){52     int x;53     char d;54     scanf("%d%d",&n,&m);55     for(int i=1;i<=n;i++)56         for(int j=1;j<=m;j++){57             scanf("%d",&x);58             if(x)59                 a[i][j]=a[i-1][j]=a[i-1][j-1]=a[i][j-1]=1;60         }61     scanf("%d%d%d%d",&sr,&sc,&er,&ec);62     scanf(" %c",&d);63     if(a[er][ec]){64         printf("-1\n");65         return 0;66     }67     tmp.r=sr,tmp.c=sc;68     switch(d){69         case 'N':tmp.dir=0;break;70         case 'E':tmp.dir=1;break;71         case 'S':tmp.dir=2;break;72         case 'W':tmp.dir=3;73     }74     tmp.step=0;75     vis[sr][sc][tmp.dir]=true;76     bfs();77     return 0;78 }