Oi_oier 2021-08-18 21:58 采纳率: 83.3%
浏览 81
已结题

一道BFS连通块问题,想了很久都不知道怎么做,第一次来CSDN问问题,希望能有人理我QAQ

不知道怎么做(っ °Д °)
题目描述:猪猪学校的草坪是长方形的,地上有的格子铺着草,有些格子则是小花。佩奇站在其中一格草地上,他只能向相邻的铺着草的格子移动,不能走到有小花的格子上。
请编写一个程序,计算佩奇能够到达的格子的数量。
输入格式:共 k+1行,

第一行是两个整数 n 和 k ,分别表示草地的宽度和高度。

在接下来的 k 行中,每行包括 n 个字符。每个字符表示当前格子的植物,规则如下

1).:草地格子;
2)#:鲜花格子;
3)@:草地格子,并且佩奇一开始站在这个格子上,全图只有一个。
输出格式:一个整数,表示佩奇能到达的格子数量(包括一开始的那格)。
样例:(输入)
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
输出:
45
数据范围:
对于 100% 的数据有1≤n,k≤20 。

  • 写回答

2条回答 默认 最新

  • 诺er~ 2021-08-18 22:54
    关注

    稍微改了一点

    
    #include<bits/stdc++.h>
    using namespace std;
    bool a[110][110];
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    struct pa
    {
        int nowx,nowy;
    }q[256];
    int main()
    {
        int n,m;
        cin>>n>>m;
        char c;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>c;
                if(c=='.') a[i][j]=1;
                else if(c=='#') a[i][j]=0;
                else 
                {
                    a[i][j]=0;
                    q[1].nowx=i;
                    q[1].nowy=j;
                }
            }
        }
        
        int f=1,r=1;
        int s=0;
        while(f<=r)
        {
            a[q[f].nowx][q[f].nowy]=0;
            for(int i=0;i<4;i++)
            {
                int xx=q[f].nowx+dx[i];
                int yy=q[f].nowy+dy[i];
                if(xx>0&&yy>0&&a[xx][yy]!=0&&xx<=n&&yy<=m)
                {
                    r++;
                    q[r].nowx=xx;
                    q[r].nowy=yy;
                    a[xx][yy]=0;
                    cout<<q[r].nowx<<" "<<q[r].nowy<<endl;
                    s++;
                }
            }
            f++;
        }
        cout<<s+1;
        return 0;
    } 
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 8月26日
  • 已采纳回答 8月18日
  • 创建了问题 8月18日

悬赏问题

  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
  • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 保护模式-系统加载-段寄存器