队列 象棋中的马 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;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)