[数据结构与算法]广搜(广度优先搜索)

// 这是按照我自己的习惯写的，可以进行稍微更改  

#include<stdio.h>

#include<queue>

using namespace std;

const int N=1e2;

int sx,sy,fx,fy;

int nex[4][2]={1,0,-1,0,0,1,0,-1};// 只能往上下左右走  

int book[N][N];// 记录是否走过，1表示已经遍历  



struct node

{

	int x,y,step;

};



void bfs()

{

	queue<node>zheng;

	node r;

	r.x=sx,r.y=sy,r.step=0;

	zheng.push(r);

	book[sx][sy]=1;

	while(!zheng.empty())

	{

		int x=zheng.front().x,y=zheng.front().y;

		if(x==fx&&y==fy)// 走到终点  

		{

			printf("%d\n",zheng.front().step);

			break;

		}

		for(int i=0;i<4;i++)

		{

			int nx=x+nex[i][0];

			int ny=y+nex[i][1];

			// 再10*10的范围内且没有走过   

			if(nx>=0&&ny>=0&&nx<10&&ny<10&&book[nx][ny]==0)

			{

				r.step=zheng.front().step+1;

				r.x=nx,r.y=ny;

				book[nx][ny]=1;

				zheng.push(r);

			}

		}

		zheng.pop();

	}

	

}



int main()

{

	// 输入起点和终点坐标 

	scanf("%d%d%d%d",&sx,&sy,&fx,&fy); 

	bfs();

	return 0;

}