bfs判断转弯次数

bfs判断转弯次数也就是顾名思义我们如何来应对需要至少转弯多少次或者计算总共转弯多少次的题目

胡乱分析

例题 P1649 [USACO07OCT]障碍路线Obstacle Course
算法核心在于对每个能到达的部分进行枚举然后进行一波更新

for(int i=0;i<4;i++)
{
  int xx=p.x+dx[i];
  int yy=p.y+dy[i];
  while(check(xx,yy))
  {
    if(step[xx][yy]>step[p.x][p.y]+1)
    {
      step[xx][yy]=step[p.x][p.y]+1;
      q.push((node){xx,yy});
    }
    xx+=dx[i];
    yy+=dy[i];
  }
}

还需要注意除了开始节点设置为-1其他节点初始化都为inf(也就是一个极大值)

完整代码

#include <bits/stdc++.h>
using namespace std;
char mp[666][666];
int sx,sy,ex,ey,f,step[666][666];
struct node
{
  int x,y;
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {
    cin>>mp[i][j];
    if(mp[i][j]=='A')
    sx=i,sy=j;
    else if(mp[i][j]=='B')
    ex=i,ey=j;
    step[i][j]=99999;
  }
  step[sx][sy]=-1;
  queue<node> q;
  q.push((node){sx,sy});
  while(q.size())
  {
    node p=q.front();
    q.pop();
    if(p.x==ex&&p.y==ey)
    {
      f=1;
      break;
    }
    for(int i=0;i<4;i++)
    {
      int xx=p.x+dx[i];
      int yy=p.y+dy[i];
      while(xx>=1&&yy>=1&&xx<=n&&yy<=n&&mp[xx][yy]!='x')
      {
        if(step[xx][yy]>step[p.x][p.y]+1)
        {
          step[xx][yy]=step[p.x][p.y]+1;
          q.push((node){xx,yy});
        }
        xx+=dx[i];
        yy+=dy[i];
      }
    }
  }
  cout<<(f?step[ex][ey]:-1);
}