这道题可以用一个特殊的BFS来求解。每次把队首元素四个方向上的点扩展到队尾，用桶来记录转弯次数。
1.初始状态
A（起点）的转弯次数为-1。
2.产生结点的规则
现在，起点位于队首。
从队首的点向四周逐“层”扩展，每一“层”扩展到的新点入队列，这些新点显然不需要转弯就可以达到（起点任意方向），所以他们的转弯次数记录为0 （也就是起点+1，你的疑问马上就会得到解答）
这就是产生新结点的策略。
3.记录每个点的转弯次数
扩展到的新点的转弯次数=队首点的转弯次数+1。（由于BFS的特点，新点未被访问过才可以被加入队尾）
下面是证明。
如果扩展到的新点是不转90°（直走）就可以到的，那该点一定被扩展了队首点的点（队首点的父结点，不知道这么说对不对）访问过，此时该点不会被当作新点处理。同理，转弯180°的点也一定被扩展了队首点的点访问过。
所以，扩展到的新点一定是转弯90°（左或右）才能走到的。
此时，到新点的转弯次数=队首点的转弯次数+1。
证明完毕。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<map> using namespace std; int n;//地图大小 int timex[200][200]={0};//转弯次数记录 int cachex,cachey,sx,sy,ex,ey;//起点，终点坐标和队首坐标缓存 int wayx[4]={-1,0,1,0},wayy[4]={0,1,0,-1};//方向表 queue<int>quex,quey; char mapx[200][200]={0};//地图 bool teller[4]={true};//扩展层数判断 void showTimex()//输出到地图各点的转弯次数 { cout<<endl<<"Showing Timex Mitrix"<<endl<<endl; for (int i=0;i<n;i++) { for (int j=0;j<n;j++) printf("%3d",timex[i][j]); printf("\n"); } printf("\n"); return; } int main() { memset(timex,-1,sizeof(timex)); scanf("%d",&n); getchar();//吸收回车 for (int i=0;i<n;i++) for (int j=0;j<n;j++) { cin>>mapx[i][j]; if (mapx[i][j]=='A'){sx=i;sy=j;}//记录起点 if (mapx[i][j]=='B'){ex=i;ey=j;mapx[i][j]='.';}//记录终点并且让终点可以入队 } //cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<" "<<endl; /*去掉注释可以看起点终点的位置*/ quex.push(sx); quey.push(sy); while (quex.size()>0) { memset(teller,true,sizeof(teller));//初始化 扩展层数判断变量 cachex=quex.front(); cachey=quey.front();//缓存存入 if (cachex==ex && cachey==ey)//如果到了终点，输出（这个题不存在起点=终点的情况，因为分别用AB表示 { cout<<timex[ex][ey]<<endl; return 0; } for (int j=0;j<=3;j++)//四个方向 { for (int i=1;i<=n;i++)/*开一层*/ if (teller[j]==true) /*如果该方向上 前面一层没遇到障碍*/ { //cout<<"Direction= "<<j<<" Now Position At: "<<cachex+wayx[j]*i<<" "<<cachey+wayy[j]*i<<endl; /*去掉注释看方向、现在扩展到的位置坐标 */ if (cachex+wayx[j]*i>=0 && cachex+wayx[j]*i<n && cachey+wayy[j]*i>=0 && cachey+wayy[j]*i<n)//越界判断 { if (mapx[cachex+wayx[j]*i][cachey+wayy[j]*i]=='.' && timex[cachex+wayx[j]*i][cachey+wayy[j]*i]==-1) //未被访问且不是障碍 { timex[cachex+wayx[j]*i][cachey+wayy[j]*i]=timex[cachex][cachey]+1;//计算转弯次数 quex.push(cachex+wayx[j]*i); quey.push(cachey+wayy[j]*i);//入队列 } else if (mapx[cachex+wayx[j]*i][cachey+wayy[j]*i]=='x') teller[j]=false;//此方向该层存在障碍，结束此方向的扩展 } else teller[j]=false;//越界，结束扩展 } } //showTimex(); /*去掉注释可以看每一次扩展完之后的转弯次数表*/ quex.pop(); quey.pop();//队首元素出队 } cout<<-1<<endl;//搜完全图，没搜到 return 0; } |