牛客算法入门课练习赛3-A 胖胖的牛牛

题意：求在地图中从A到B的最小转弯次数
题解：很明显的一个搜索题，这里我的做法采用dfs，dfs里面保存状态x,y,t,fa,分别代表当前位置的x，y,已经转弯次数，上次行走的方式。然后从A dfs到B，详细步骤可查看代码注释

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
char Map[N][N];
int ans,n;
int sx,sy,ex,ey;
int change[4][2]={1,0,-1,0,0,1,0,-1};
int vis[N][N];
bool legal(int x,int y){
    if (x>=1&&x<=n&&y>=1&&y<=n)
        return 1;
    return 0;
}
void dfs(int x,int y,int t,int fa){
     if (x==ex&&y==ey){//终点判断
         ans=min(ans,t);
         return;
     }
     if (t>=ans)//这里没有就会超时
         return;
     for (int i=0;i<4;i++){
     if (!legal(x+change[i][0],y+change[i][1]))
         continue;
     if (Map[x+change[i][0]][y+change[i][1]]=='x')
         continue;
          if (vis[x+change[i][0]][y+change[i][1]]==0){
               vis[x+change[i][0]][y+change[i][1]]=1;
               if (fa!=-1&&i!=fa)
               dfs(x+change[i][0],y+change[i][1],t+1,i);
              else
               dfs(x+change[i][0],y+change[i][1],t,i);
               vis[x+change[i][0]][y+change[i][1]]=0;//dfs的回溯
          }
     }
}
int main(){
    scanf("%d%*c",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%c",&Map[i][j]),getchar();
    for (int i=1;i<=n;i++)//这步可以省略到前面的读入，分开写也一样
        for (int j=1;j<=n;j++)
            if (Map[i][j]=='A')
                sx=i,sy=j;
            else if (Map[i][j]=='B')
                ex=i,ey=j;
    ans=1e9;//初始化一个比较大的值就可以了，不一定是1e9。
    dfs(sx,sy,0,-1);
    if (ans!=1e9)//存在找不到的情况，如果你样例通过率90%，就大概是这问题
    cout<<ans<<endl;
    else
        puts("-1");
    return 0;
}