牛客 NC208246 胖胖的牛牛
题目描述
每逢佳节胖三斤，牛牛在过去的节日里长胖了，连拐弯都困难，甚至会卡在门上，所以他很讨厌拐弯。给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。
输入描述:
第一行一个整数：N，下面N 行，每行N 个字符，只出现字符：‘.’，‘x’，‘A’，‘B’；表示上面所说的矩阵格子，每个字符后有一个空格。
输出描述:
一个整数：最少转弯次数。如果不能到达，输出-1。示例1
输入
复制
3 . x A . . . B x .输出
复制
2备注:
开始和结束时的方向任意。
思路：要求最小的转向次数，可以用深度优先搜索加优先队列，队列按照转向次数从小到大排序，每次入队当前点坐标和前驱点坐标以及到当前点的转向次数，在出队时将相关点标记不再搜索，第一次遍历到终点的转向次数即是答案；
因为只要存在转向那么下一点的x和y坐标必与前驱点的x和y坐标不同，于是我们可以利用前驱点坐标来判断是否转向；
AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=110;
char mp[N][N];
int n,m,sx,sy,ex,ey;
bool st[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
struct Node
{
int x,y,px,py;
int cnt;
bool operator<(const Node&t)const
{
return cnt>t.cnt;
}
};
int bfs()
{
priority_queue<Node> q;
q.push({sx,sy,sx,sy,0});
st[sx][sy]=1;
while(q.size())
{
Node t=q.top();
q.pop();
int x=t.x,y=t.y;
if(x==ex&&y==ey)return t.cnt;
st[x][y]=1;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||xx>n-1||yy<0||yy>n-1)
continue;
if(mp[xx][yy]=='x'||st[xx][yy])
continue;
int isTurn=(t.px!=xx&&t.py!=yy);
q.push({xx,yy,x,y,t.cnt+isTurn});
}
}
return -1;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='A')
sx=i,sy=j;
if(mp[i][j]=='B')
ex=i,ey=j;
}
cout<<bfs()<<endl;
}