问题标题: 哪位大神给我看看哪里错了?C++酷丁堂2085

0
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
洪朝阳
洪朝阳
修练者
修练者

dir开错了不影响,但BFS之前队列要清空

 

0
0
我要回答