乳草的入侵

acwing189
破例发道简单题

题目描述

由于作者太懒,请自行看题。

解题思路

乍一看是一个非常简单的BFS,然后我就写了一边,测试数据一遍就过了。

可能是出题人想增加一下题目难度,脑子一抽,x变成了列,y变成了行。

不过这一点再题目样例中可以看出来。最毒瘤的是mx变成列,my变成行,题目中还没有写。。。

代码

#include<bits/stdc++.h>
using namespace std;
char m[105][105];
int st[105][105];
bool vis[105][105];
int gx[8]={1,1,1,0,0,-1,-1,-1};
int gy[8]={1,0,-1,1,-1,1,0,-1};
struct kkk{
    int xx,yy,t;
};
queue<kkk> q;
int cnt=1;
int ans=0;
int main(){
    int x,y,mx,my;
    cin>>x>>y>>mx>>my;
    for(int i=1;i<=y;i++){
        for(int j=1;j<=x;j++){
            cin>>m[i][j];
            if(m[i][j]=='*'){
                cnt++;
            } 
        }
    }
    kkk nxt;
    kkk now;
    now.xx=y-my+1,now.yy=mx,now.t=0;
//    cout<<now.xx<<" "<<now.yy<<endl;
    q.push(now);
    vis[y-mx+1][my]=1;
    while(!q.empty()){
        now=q.front();
        q.pop();
        bool tf=0;
        for(int i=0;i<8;i++){
            if(!vis[now.xx+gx[i]][now.yy+gy[i]]&&now.xx+gx[i]<=y&&now.yy+gy[i]<=x&&now.xx+gx[i]>=1&&now.yy+gy[i]>=1){
                if(m[now.xx+gx[i]][now.yy+gy[i]]=='.'){
                    st[now.xx+gx[i]][now.yy+gy[i]]=now.t+1;
                    vis[now.xx+gx[i]][now.yy+gy[i]]=1;
                    nxt.xx=now.xx+gx[i],nxt.yy=now.yy+gy[i],nxt.t=now.t+1;
                    cnt++;
                    if(cnt==x*y){
                        cout<<nxt.t<<endl;
/*                        for(int i=1;i<=y;i++){  
                            for(int j=1;j<=x;j++){
                                cout<<st[i][j];
                            }
                            cout<<endl;
                        }
*/                        tf=1;
                        break;
                    }
                    q.push(nxt);
                }
            }
        }
        if(tf){
            break;
        }
    }
    return 0;
} 

本文链接:https://kaispace.com.cn/index.php/archives/497/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者