0
已解决
于子轩
初级守护
初级守护
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int dir[12][12] = {
{-2,-2},{-1,-2},{-2,-1},
{-2,2},{-2,1},{-1,2},
{2,-2},{1,-2},{2,-1},
{2,2},{2,1},{1,2},
};
struct coord {
int x,y,count;
};
queue<coord> q;
bool visited[101][101];
bool canJump(int x,int y)
{
if(x>=1 && x<=100 && y>=1 && y<=100) return true;
return false;
}
int bfs(int x, int y) {
q.push((coord){x,y,0});
while(!q.empty())
{
coord now =q.front();
q.pop();
if(now.x == 1 && now.y == 1) return now.count;
for(int i=0;i<12;i++)
{
int nx = now.x + dir[i][0];
int ny = now.y + dir[i][1];
if(canJump(nx,ny) && !visited[nx][ny]) {
visited[nx][ny]=true;
q.push((coord){nx,ny,now.count+1});
}
}
}
//return
}
int main()
{
int a,b,c,d;
cin>>a>>b;
cin>>c>>d;
memset(visited,false,sizeof(visited));
visited[a][b] = true;
cout<<bfs(a,b)<<endl;
memset(visited,false,sizeof(visited));
visited[c][d] = true;
cout<<bfs(c,d)<<endl;
return 0;
}
先到先得,AC100者 @BFS内队列怎么清空(方法)?
3
已采纳
王安川
初级守护
初级守护
一、走马的步数应改为
const int dir[12][2]={
{-2,-2},{-1,-2},{-2,-1},
{-2,2},{-2,1},{-1,2},
{2,-2},{1,-2},{2,-1},
{2,2},{2,1},{1,2}
};
二、BFS函数开头遗漏
应改为: while(!q.empty())//判断队列q是否空
q.pop();//首先要清零
q.push((coord){x,y,0});//存入结构体
5
陶梓锐
新手光能
新手光能
const int dir[12][12] = {
{-2,-2},{-1,-2},{-2,-1},
{-2,2},{-2,1},{-1,2},
{2,-2},{1,-2},{2,-1},
{2,2},{2,1},{1,2},
};
错了,应该是:
const int dir[12][2] = {
{-2,-2},{-1,-2},{-2,-1},
{-2,2},{-2,1},{-1,2},
{2,-2},{1,-2},{2,-1},
{2,2},{2,1},{1,2},
};
+加BFS内队列要清空
2
1
0
0