BFS 30pts求调
  • 板块P1443 马的遍历
  • 楼主LiaoYF1
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/14 19:17
  • 上次更新2023/10/27 20:20:36
查看原帖
BFS 30pts求调
633466
LiaoYF1楼主2022/7/14 19:17
#include<iostream>
#include <cstring>
#include<queue>
using namespace std;
int n,m,x,y,ans[405][405];//ans存答案
const int dx[8]={-1,-1,-2,-2,1,1,2,2};//方向
const int dy[8]={2,-2,-1,1,2,-2,-1,1};
bool vis[405][405];//vis为该位置是否走过
inline bool ok(int xx,int yy){//是否可走
    return xx>=1&&xx<=n&&yy>=1&&yy<=m;
}
queue<int> qx,qy;//两个队列存x和y
int main(){

    cin>>n>>m>>x>>y;
    //memset(ans,-1,sizeof(ans));
    qx.push(x);qy.push(y);//加入起点
    vis[1][1]=1;//起点标记为访问过
    while(!qx.empty()){//DFS
        //cout<<qx.front()<<" "<<qy.front()<<endl;
        int nx=qx.front(),ny=qy.front();
        qx.pop();qy.pop();
        for(int i=0;i<8;i++){
            int xx=nx+dx[i],yy=ny+dy[i];
            if(ok(xx,yy)&&!vis[xx][yy]){//可走且没走过
                vis[xx][yy]=1;//标记
                qx.push(xx);qy.push(yy);//入队
                ans[xx][yy]=ans[nx][ny]+1;//计算结果
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",vis[i][j]?ans[i][j]:-1);//如果访问过就输出ans[i][j],否则输出-1
        }
        printf("\n");
    }
    return 0;
}

记录

2022/7/14 19:17
加载中...