【队列】 象棋中的马 BFS C++ (接上一篇文章)

【队列】 象棋中的马 BFS C++ (接上一篇文章),第1张

队列 象棋中的马 BFS C++ (接上一篇文章)
不同于迷宫,迷宫中有通道和障碍;而象棋中的马则没有明显标记的通道和障碍。



因此要标记该点是否入过队 inq[x][y]={false}; 默认没有入过队
输入:x1,y1起点坐标 x2,y2终点坐标
5 4 7 8
输入:需要走的步数
2

#include 
using namespace std;

int step[10][11]={0};
//输入起点、终点
int sx,sy,ex,ey;
bool inq[10][11]={false};//没入过队的是false 
typedef struct point {
	int x;
	int y;
}node;
node start;
int dxy[8][2]={{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};

bool test(int newx,int newy)
{
	//超出棋盘格 
	if(newx<1 || newx>9 || newy<1 || newy>10){
		return false;
	}
	//已经入过队 
	if(inq[newx][newy]==true){
		return false;
	}
	return true;
}

void bfs()
{
	queue <node> q;
	//起点入队
	q.push(start);
	
	while(!q.empty()){
		node top=q.front();
		q.pop();
		//看看是否到达终点
		if(top.x==ex && top.y==ey){
			cout<<step[top.x][top.y]<<endl;
			return ;
		}else {
			for(int i=0;i<8;i++){//8个位置可走 
				int newx=top.x+dxy[i][0];
				int newy=top.y+dxy[i][1];
				//test(newx,newy) 该位置可 
				if(test(newx,newy)){
					step[newx][newy]=step[top.x][top.y]+1;//步数+1
					node n;
					n.x=newx;
					n.y=newy;
					q.push(n);//把该结点入队 
					inq[n.x][n.y]=true;//标记已经入队 
				}
			}
		}
	}
	cout<<"0"<<endl;
	return ;
}

int main()
{	
	//输入起点、终点
	cin>>sx>>sy>>ex>>ey;
	start.x=sx;
	start.y=sy;
	
	step[sx][sy]=0;//起点步数为0
	inq[sx][sy]=true;//起点入队 
	bfs();
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/578235.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-11
下一篇 2022-04-11

发表评论

登录后才能评论

评论列表(0条)

保存