记录编号	531990	评测结果	AWAAAAAWAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct07] 障碍训练场	最终得分	92
用户昵称	斯内普和骑士	是否通过	未通过
代码语言	C++	运行时间	0.034 s
提交时间	2019-05-22 17:05:32	内存使用	13.90 MiB

#include<bits/stdc++.h>
using namespace std;
const int RUA=101;
struct pd
{
    int x;
    int y;
}hrb[20050];//队列，保存状态 
int lxy[RUA][RUA],emm[RUA][RUA];//lxy起到bool 作用，emm记录拐弯次数 
int n,m,i,j,k,l;
int r=1;
int x,y;
char tu[RUA][RUA];//原图 
int xy[4]={1,-1,0,0},yx[4]={0,0,-1,1};//坐标变量 
int main()
{
	freopen("obstacle.in","r",stdin);
    freopen("obstacle.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
    	for(int k=1;k<=n;k++)
    	{
    		cin>>tu[i][k];
    		if(tu[i][k]=='A')
    		{
    			hrb[l].x=i;
    			hrb[l].y=k;
    			lxy[i][k]=1;
    		}
    		if(tu[i][k]=='B')
    		{
    			x=i;
    			y=k;
    		}
    		if(tu[i][k]=='x')
    		lxy[i][k]=1;
    		//对图进行处理，障碍物和起点为1，表示什么就不用再解释了 
    	}
    while(l<r)//暴搜开始 
    {
    	for(i=0;i<4;i++)//枚举坐标变量，四个方向，左上右下移动 
    	for(k=1;;k++)
    	{
    		int xx=hrb[l].x+k*xy[i],yy=hrb[l].y+k*yx[i];
            //枚举一个常数k，与坐标变量相乘
            if(lxy[xx][yy]==1)break;
            if(xx<=0||xx>n||yy<=0||yy>n)break;
            //碰边或走过了，停止填充
            lxy[xx][yy]=1;//打标记
            emm[xx][yy]=emm[hrb[l].x][hrb[l].y]+1;
            //停了，说明该转弯了，于是当前点的次数为原坐标的加1
            hrb[r].x=xx;
            hrb[r].y=yy;
            r++;//进行队列
    	} 
    	l++;
    }
    if(emm[x][y]!=0)
    printf("%d",emm[x][y]-1);
    else
    cout<<"-1";
    return 0;
}