岛屿问题

#include <iostream>
#include <vector>
using namespace std;

int m = 4, n = 5;
int MaxLand = 0;            //最大岛屿
int temp = 0;

//使用DFS求岛屿个数和最大岛屿,如果当前位置为1，则将岛屿数量加1，然后将该位置设置为0，然后搜索该位置的上下左右位置，若为1，则设置为0并搜索知道四周都为0
void DFS(vector<vector<bool>>& arr, int i, int j)
{
    if (i < 0 || i >= m || j < 0 || j >= n || !arr[i][j])       //到了边界返回
    {
        return;
    }
    temp++;
    arr[i][j] = false;                      //当前位置置为0

    DFS(arr, i - 1, j);                     //遍历上
    DFS(arr, i + 1, j);                     //遍历下
    DFS(arr, i, j - 1);                     //遍历左
    DFS(arr, i, j + 1);                     //遍历右

}

//使用DFS求最大岛屿周长
vector<bool> visited;
int DFS_Perimeter(vector<vector<bool>>& arr, int i, int j)
{

    if (i < 0 || i >= m || j < 0 || j >= n || !arr[i][j])                   //边界为岛屿的周长的一部分
    {
        return 1;
    }

    if (arr[i][j] && visited[i * n + j])                                    //如果该位置已经被访问且为1，说明在岛屿中间
    {
        return 0;
    }

    visited[i * n + j] = true;                                              //标志该位置已经被访问过

    return DFS_Perimeter(arr, i - 1, j) + DFS_Perimeter(arr, i + 1, j)      //上边界+下边界+左边界+右边界
        + DFS_Perimeter(arr, i, j - 1) + DFS_Perimeter(arr, i, j + 1);
}

int main(int argc, char** argv)
{
    //step1:随机生成一个二维数组

    vector<vector<bool>> arr;
    arr.resize(m);
    for (int i = 0; i < m; i++)
    {
        arr[i].resize(n);
        for (int j = 0; j < n; j++)
        {
            arr[i][j] = rand() % 2;
        }
    }

    //step2:打印数组
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    //step3:计算岛屿数量、最大岛屿面积和周长
    visited.resize(m * n);                  //初始化标志该位置未被访问
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] && !visited[i * n + j])                   //如果该位置为1且没有被访问，则对该岛屿进行DFS搜索
            {
                //计算岛屿数量和最大岛屿
                //count++;
                //DFS(arr, i, j);

                //if (temp > MaxLand)
                //{
                //  MaxLand = temp;
                //}

                //temp = 0;

                //计算岛屿周长
                int temp = DFS_Perimeter(arr, i, j);
                if (temp > MaxLand)
                {
                    MaxLand = temp;
                }

            }
        }
    }

    //cout << "岛屿个数：" << count << endl;
    //cout << "最大岛屿面积：" << MaxLand << endl;

    cout << "最大岛屿周长:" << MaxLand << endl;

    return 0;
}