广度优先搜索算法3-例8.3 最少步数
例子8.3 最少步数
在各种棋中，棋子的走法总是一定的，如中国象棋马走日。
有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他归档马既能按日走，也能如象一样走田字。
在一个100*100的围棋盘上任选连点A.B。A点放上黑子，B点放上白子，代表两匹马。
棋子可以走日字也可以走田字，两个人一个人走 黑马，一个人走白马。
谁用最少的步数走到左上角坐标为（1，1）的点时，谁就获胜。
现在他请你帮忙，给你A,B两点坐标，想知道两个位置到（1，1）点可能的最少步数。
算法分析：
由于A,B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解
1.先确定出发点
从（x,y)出发通过一次广度优先搜索，可以找到从（x,y)至棋盘上所有可达到点的最少步数。
而问题中要求的是黑马所在的位置（x1,y1)和白马所在的位置（x2,y2)到达（1，1）目标点的最少步数。
虽然两点的路径起点不一样，但是他们的终点是一样的。
如果将终点（1，1）作为起点，这样只需要一次广度优先搜索便可以得到（x1,y1)和（x2,y2)到达（1，1）的最少步数
2.数据结构
设queue-队列，存储从（1，1)而可到达的点（queue[k][1..2])
以及到达该点所需要的最少步数（queue[k][3])(0<=k<=192+1).
队列的首指针为head尾指针为tail.
初始时，只有一个元素为（1，1），最少步数为0
s-记录（1，1）到每点所需要的最少步数。显然问题的答案是s[x1][y1]和s[x2][y2]
初始时，s[1][1]为0，除此之外的所有元素值设为-1
dx,dy-移动后的位置增量数组。也就是以目前到达的点（x,y)为原点，360度扫描可以走的坐标，将其进行加减就可以了
3.约束条件
（1）不能越出界外。一旦超出s的范围，就将其s值赋值为0
（2）该点在以前的扩展中没有出现过。
如果曾经到达过，则根据广度优先搜索的原理，先到达该点所需的步数一定小于当前步数。
#include
#include
using namespace std;
//定义增量
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
//主函数
int main(){
//初始位置入队
int head=1,tail=1;
//s数组用于存放每点到各点的最少步数，que数组用于存放原点可到达的点
int s[101][101],que[10000][4]={0};
//x,y用于记录走日字或田字的坐标
int x1,y1,x2,y2;
//s数组初始化
memset(s,0xff, sizeof(s));
que[1][1]=1;
que[1][2]=1;
que[1][3]=0;
cin>>x1>>y1>>x2>>y2;//读入黑马和白马的位置
//BFS实现
//队列非空则扩展首节点
while(head<=tail){
//枚举12个扩展方向
for (int d = 0; d 0&&y>0){
//判断该点是否走过
if(s[x][y]==-1){
//计算起点到该点的最少步数
s[x][y]=que[head][3]+1;
//起点到该点的最少步数入队
tail++;
que[tail][1]=x;
que[tail][2]=y;
que[tail][3]=s[x][y];
//输出问题的解
if(s[x1][y1]>0&&s[x2][y2]>0){
cout<<s[x1][y1]<<endl;
cout<<s[x2][y2]<<endl;
system("pause");
return 0;
}
}
}
}
head++;
}
}
总结：和上一篇细胞计数类似，原理都差不多，都是坐标的加减变换位置
作者：qew2017
