关于这道深度优先遍历的问题，如何解决？（C++）

Question

【问题描述】
给你一块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++如何用深度优先搜索解决呢

Answer 1

你题目的解答代码如下：

#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;
}

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