大家来扫雷

大家来扫雷

http://www.nowcoder.com/questionTerminal/2104cdc2aa464befac72868421066fcb

题解:

考察点: 搜索

题解:

如果最开始位置是炸弹,则不存在可扩展的可能性,一定输出。否则其他情况一定是可以扩展的。采用广度优先搜索进行坐标的扩展。对于一个位置,对其周围个方向进行遍历,如果有越界,或者不能扩展的位置,则剪掉;如果周围个方向存在数字为的,则将其加入队列,作为新的进行新一轮的扩展,直到所有的点都遇到数字边界或者地图边界。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
const int maxn=1e3+10;
int n,m,x,y;
char s[maxn][maxn];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int Count(int x,int y){
    int cnt=0;
    for(int i=0;i<8;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(s[nx][ny]=='*') cnt++;
    }
    s[x][y]=cnt+'0';
    return cnt;
}
void bfs(int x,int y){
    queue<P>que;
    que.push(make_pair(x,y));
    while(!que.empty()){
        P t=que.front();
        que.pop();
        for(int i=0;i<8;i++){
            int nx=t.first+dx[i],ny=t.second+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]!='.') continue;
            int num=Count(nx,ny);
            if(num==0) que.push(make_pair(nx,ny));
        }
    }
}
int main()
{
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    if(s[x][y]=='*') cout<<"GG"<<endl;
    else{
        if(Count(x,y)==0) bfs(x,y);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cout<<s[i][j];
            cout<<endl;
        }
    }
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:00
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务