c++ 广度优先搜索(宽搜)

c++ bfs基本应用

Knight Moves

题目描述

贝茜和她的表妹在玩一个简化版的国际象棋。棋盘如图所示：

贝茜和表妹各有一颗棋子。棋子每次移一步，且棋子只能往如图所示的八个方向移动。比赛的规则很简单，两个人需要从起点将棋子移到终点，谁能花最少的步数从起点走到终点，就是赢家。

为了确保能赢表妹，贝茜希望每次都能算出最少的步数，你能帮助她么？

输入

输入起点和终点，用一个空格隔开。（确保起点一定能走到终点）

输出

输入最少的步数。

样例输入

a1 b2

样例输出

上代码:

AC代码

#include <bits/stdc++.h>

using namespace std;

struct Point

{

	int x,y,step;

};

Point q[1000000],s,t;//t是终点,s是起点

int dx[8]={1,-1,1,-1,2,2,-2,-2};//dx[] + dy[] 代表Knight走的8个方向可达的点

int dy[8]={2,2,-2,-2,1,-1,1,-1};

int f=1,e=0;

int main()

{

	char ca,cb,cc,cd;

	scanf("%c%c %c%c",&ca,&cb,&cc,&cd);//输入

	s.x=ca-'a'+1,s.y=cb-'1'+1;s.step=0;//把a转换成数字1 把字符1转换成数字1

	t.x=cc-'a'+1,t.y=cd-'1'+1;t.step = 0;//把b转换成数字2 把字符2转换成数字2

	if(s.x==t.x&&s.y==t.y)//如果起点等于终点,就直接退出

	{

		printf("0\n");

		return 0;

	}

	e++;//队列入队时候的下标

	q[e]=s;//q就是队列 把所有待查找的元素放在q队列里面 首先把第一个骑士s放在q队列里的第一个位置

////////////////////////////////开始宽搜////////////////////////////////////////////////

	while(f<=e)//出队的下标不能大于入队时候的下标

	{

		Point u=q[f];//f是队列出队时候的下标      //* u是在队列中选定的骑士 *//////////////注意！！！！！！！此处下标为f!!!!!!!!!///

		for(int i=0;i<8;i++)//for循环为了能 加上dx[] 和dy[]

		{

		    Point v;//v是有效的骑士

		    v.x = u.x + dx[i],v.y = u.y + dy[i],v.step=u.step + 1;//把选定的位置向8个方向扩展(一次)

		    if(v.x<1||v.x>8||v.y<1||v.y>8)continue;//如果这个骑士的位置不在棋盘上,则丢弃

		    if(t.x==v.x&&t.y==v.y)//找到了终点

		    {

		    	printf("%d\n",v.step);//输出步数

		    	return 0;

			}

		    e++;// 把入队下标 + 1

		    q[e]=v;//  入队

	    }

	    f++;//出队下标 + 1

	}

	return 0;

}

BFS思路总结：

step1：先找出所有符合规则的数，通过走棋规则和棋盘的边界来过滤

step2：将有效的数入队，入队的同时进行比较是否达到终点

step3：最后输出走到终点时的step

巴特西