代码随想录：104. 建造最大岛屿

104. 建造最大岛屿

这题我们先标记一下岛屿，用记号标记并统计它的面积。

然后遍历每一个海水，将它四周岛屿面积加起来取最大值。

1、条件准备

tag数组用来存该位置的陆地被标记成第几块

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'

int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
int tag[100][100];

2、主函数

先存图。visit数组标记该块是否走过，ma用来存该标记的岛面积是多大。

num为第几块岛。

然后遍历图，算每一块岛屿的面积，并与标记匹配。

最后遍历每一块海水，遍历四周算面积和，集合s保证不算到重复标记的岛屿。

如果ant没有变，证明全为岛屿，则输出n*m，否则输出ant

int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  vector<vector<int>> graph(n, vector<int>(m, 0));

  rep(i, 0, n - 1)
          rep(j, 0, m - 1)
              cin >>graph[i][j];
  vector<vector<bool>> visit(n, vector<bool>(m, 0));
  unordered_map<int, int> ma;
  int num = 1;
  rep(i, 0, n - 1)
      rep(j, 0, m - 1) if (!visit[i][j] && graph[i][j])
  {
    ma[num] = dfs(graph, visit, i, j, num);
    num++;
  }

  int ant = 0;
  rep(i, 0, n - 1)
      rep(j, 0, m - 1)
  {
    if (!graph[i][j])
    {
      vector<int> squ(4, 0);
      set<int> s;
      for (int k = 0; k < 4; k++)
      {
        int xx = i + dir[k][0], yy = j + dir[k][1];
        if (xx < 0 || yy < 0 || xx >= n || yy >= m)continue;
        if (s.find(tag[xx][yy]) != s.end())continue;
        squ[k] = ma[tag[xx][yy]];
        s.insert(tag[xx][yy]);
      }
      ant = max(ant, squ[0] + squ[1] + squ[2] + squ[3] + 1);
    }
  }

  cout << (ant == 0 ? n * m : ant);
  return 0;
}

3、dfs函数

tag存该块陆地属于第几块岛。square返回岛屿面积。

int dfs(vector<vector<int>> &graph, vector<vector<bool>> &visit, int x, int y, int num)
{
  visit[x][y] = 1;
  tag[x][y] = num;
  int square = 1;
  for (int i = 0; i < 4; i++)
  {
    int xx = x + dir[i][0], yy = y + dir[i][1];
    if (xx < 0 || yy < 0 || xx >= n || yy >= m)continue;
    if (!visit[xx][yy] && graph[xx][yy])
      square += dfs(graph, visit, xx, yy, num);
  }
  return square;
}

原文地址：https://blog.csdn.net/qq_74924951/article/details/142690804

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！