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

int m = 4, n = 5;
int MaxLand = 0;            //最大島嶼
int temp = 0;

//使用DFS求島嶼個(gè)數(shù)和最大島嶼,如果當(dāng)前位置為1，則將島嶼數(shù)量加1，然后將該位置設(shè)置為0，然后搜索該位置的上下左右位置，若為1，則設(shè)置為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;                      //當(dāng)前位置置為0

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

}

//使用DFS求最大島嶼周長(zhǎng)
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])                   //邊界為島嶼的周長(zhǎng)的一部分
    {
        return 1;
    }

    if (arr[i][j] && visited[i * n + j])                                    //如果該位置已經(jīng)被訪問(wèn)且為1，說(shuō)明在島嶼中間
    {
        return 0;
    }

    visited[i * n + j] = true;                                              //標(biāo)志該位置已經(jīng)被訪問(wèn)過(guò)

    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:隨機(jī)生成一個(gè)二維數(shù)組

    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:打印數(shù)組
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    //step3:計(jì)算島嶼數(shù)量、最大島嶼面積和周長(zhǎng)
    visited.resize(m * n);                  //初始化標(biāo)志該位置未被訪問(wè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且沒(méi)有被訪問(wèn)，則對(duì)該島嶼進(jìn)行DFS搜索
            {
                //計(jì)算島嶼數(shù)量和最大島嶼
                //count++;
                //DFS(arr, i, j);

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

                //temp = 0;

                //計(jì)算島嶼周長(zhǎng)
                int temp = DFS_Perimeter(arr, i, j);
                if (temp > MaxLand)
                {
                    MaxLand = temp;
                }

            }
        }
    }

    //cout << "島嶼個(gè)數(shù)：" << count << endl;
    //cout << "最大島嶼面積：" << MaxLand << endl;

    cout << "最大島嶼周長(zhǎng):" << MaxLand << endl;

    return 0;
}