BFS 80求调
查看原帖
BFS 80求调
1129659
Kevin626楼主2024/7/25 20:19
#include<iostream>
#include<queue>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//搜索  BFS
//BFS第一次搜到就是最优;

const int N=101;
struct node{
    int x,y;
};
int x1,y1,x2,y2;
queue<node> que;
int f[N][N];
bool vis[N][N];
const int dx[]={2,2,2,2,1,1,-1,-1,-2,-2,-2,-2};
const int dy[]={-2,-1,1,2,-2,2,-2,2,-2,-1,1,2};

int main(){
    cin>>x1>>y1>>x2>>y2;
    //先搜黑马,再搜白马
    //搜索黑马走到1,1要几部
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            f[i][j]=-1,vis[i][j]=false;
    f[x1][y1]=0;
    vis[x1][y1]=1;
    que.push({x1,y1});
    //BFS开始搜索
	bool flag=0;
    while(!que.empty())
    {
        //取元素,出队列
        node cnt=que.front();
        que.pop();
        for(int i=0;i<12;i++)
        {
            int xx=cnt.x+dx[i];
            int yy=cnt.y+dy[i];
            if(!vis[xx][yy]&&xx>=1){
            	if(xx==1&&yy==1){
            		cout<<f[cnt.x][cnt.y]+1<<'\n';
            		flag=1;
            		break;
				}
                que.push({xx,yy});
                f[xx][yy]=f[cnt.x][cnt.y]+1;
                vis[xx][yy]=1;
            }
        }
        if(flag)break;
    }
    while(!que.empty())
    	que.pop();
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            f[i][j]=-1,vis[i][j]=false;
    //搜索白马走到1,1要走几步
    f[x2][y2]=0;
    vis[x2][y2]=1;
    que.push({x2,y2});
    //BFS开始搜索
    while(!que.empty())
    {
        //取元素,出队列
        node cnt=que.front();
        que.pop();
        for(int i=0;i<12;i++)
        {
            int xx=cnt.x+dx[i];
            int yy=cnt.y+dy[i];
            if(!vis[xx][yy]&&xx>=1){
            	if(xx==1&&yy==1){
            		cout<<f[cnt.x][cnt.y]+1;
            		return 0;
				}
                que.push({xx,yy});
                f[xx][yy]=f[cnt.x][cnt.y]+1;
                vis[xx][yy]=1;
            }
        }
    }
    return 0;
}

有什么问题呀,请路过大神帮忙看看 (磕头磕头磕头);(习惯了)

2024/7/25 20:19
加载中...