1 条题解

  • 0
    @ 2025-10-27 19:19:00

    这是一道按步走的bfs题目,对于每次询问,很容易知道,只要k与最短步数之差是偶数,就肯定满足k步到达目标点。

    按步走有很多种方法实现,比如说

    1. 用结构体存储步数和x,y坐标
    2. 用一个新的二维数组存储每一个点的最小步数
    3. 在bfs的队列循环种添加步数变量(需要脑力足够,不然很容易出错)

    每一种办法都可以用,能得到结果就好

    #include<bits/stdc++.h>
    using namespace std;
    struct dian{
        int x,y,bushu;
    };
    
    
    int main() {
        int n,m;scanf("%d %d",&n,&m);
        int ydx[4]={0,0,1,-1};
        int ydy[4]={1,-1,0,0};
        vector<vector<char>> ditu(n,vector<char>(m));
        vector<vector<bool>> vis(n,vector<bool>(m,false));
        vector<vector<int>> shuzi(n,vector<int>(m,-1));
        pair<int,int> qidian,zhongdian;
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            for(int j=0;j<m;j++){
                ditu[i][j]=s[j];
                if(ditu[i][j]=='B'){
                    qidian={i,j};
                }
                if(ditu[i][j]=='E'){
                    zhongdian={i,j};
                }
            }
        }
    
        queue<dian> q;
        dian axx={qidian.first,qidian.second,0};
        q.push(axx);
        vis[qidian.first][qidian.second]=true;
        shuzi[qidian.first][qidian.second]=0;
        while(!q.empty()){
            auto acc=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int nx=acc.x+ydx[i];
                int ny=acc.y+ydy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]&&ditu[nx][ny]!='#'
                &&shuzi[nx][ny]==-1){
                   shuzi[nx][ny]=acc.bushu+1;
                   vis[nx][ny]=true;
                   q.push({nx,ny,acc.bushu+1});
                }
            }
        }
    
        int asdf;
        scanf("%d",&asdf);
        int bushushu=shuzi[zhongdian.first][zhongdian.second];
    
        for(int i=0;i<asdf;i++){
            long long k;
            cin>>k;
            if(bushushu==-1){
                printf("NO\n");
            }
            else if(k>=bushushu&&(k-bushushu)%2==0){
                printf("YES\n");
            }
            else{
                printf("NO\n");
            }
        }
        return 0;
    }
    

    信息

    ID
    626
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    478
    已通过
    51
    上传者