m0_58775739 2022-03-23 12:15 采纳率: 100%
浏览 38
已结题

关于这道深度优先遍历的问题,如何解决?(C++)

【问题描述】
给你一块nm的草坪,问如果只点一次火,最多能烧多少块草坪。可以从nm的草地中任意一个地方开始点火,火只能往上下左右传递,没有草的地方不能燃烧。
【输入格式】
输入由多个测试例组成。每个测试例的第一行含两个整数n和m, (1 <=n,m<=100), 分别表示01矩阵的行数与列数,
后面紧跟着n行,每行含m个整数0或1,1代表草坪,0表示啥也没有,相邻两个整数之间用一个空格隔开,两个测
试例之间用一个空行隔开,最后一个测试例之后隔一个空行,最后一行含有两个整数0,表示输入结束。
【输出格式】
每个测试例对应一行输出,含一个整数,表示只点一次火最多能烧的草坪个数。
【样例输入】
5 6
0 1 1 0 0 1
1 1 0 1 0 1
0 1 0 0 1 0
0 0 0 1 1 1
1 0 1 1 1 0

0 0
【样例输出】
7
【提示】
深度优先搜索DFS的应用

请问C++如何用深度优先搜索解决呢

  • 写回答

2条回答 默认 最新

  • 关注

    你题目的解答代码如下:

    #include <iostream>
    using namespace std;
    
    int a[100][100];
    int ds[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int n, m;
    
    int dfs(int y,int x)
    {
        if (y<0 || y>=n || x<0 || x>=m || a[y][x]!=1)
            return 0;
        int i,sum = 1;
        a[y][x] = 0;  //这块草坪已经烧过了
        for (i = 0; i < 4; i++)
        {
            sum += dfs(y+ds[i][0], x+ds[i][1]);
        }
        return sum;
    }
    
    int main()
    {
        int i, j, d, max;
        while (true)
        {
            cin >> n >> m;
            if (n == 0 && m == 0)
                break;
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    cin >> a[i][j];
                }
            }
            max = 0;
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    if (a[i][j] == 1)
                    {
                        d = dfs(i, j);
                        if (d > max)
                            max = d;
                    }
                }
            }
            cout << max << endl;
        }
        return 0;
    }
    
    

    img

    如有帮助,请点击我的回答下方的【采纳该答案】按钮帮忙采纳下,谢谢!

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月2日
  • 已采纳回答 3月25日
  • 创建了问题 3月23日

悬赏问题

  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算
  • ¥15 powerbuilder中的datawindow数据整合到新的DataWindow
  • ¥20 有人知道这种图怎么画吗?
  • ¥15 pyqt6如何引用qrc文件加载里面的的资源
  • ¥15 安卓JNI项目使用lua上的问题
  • ¥20 RL+GNN解决人员排班问题时梯度消失
  • ¥60 要数控稳压电源测试数据
  • ¥15 能帮我写下这个编程吗
  • ¥15 ikuai客户端l2tp协议链接报终止15信号和无法将p.p.p6转换为我的l2tp线路