[Vssue]kamacoder/0104.建造最大岛屿.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0104.%E5%BB%BA%E9%80%A0%E6%9C%80%E5%A4%A7%E5%B2%9B%E5%B1%BF.html

[DEZREMNACUI]

图一乐

import { createInterface } from "readline/promises";

const rl = createInterface({
  input: process.stdin,
});

const readline = async () =>
  (await rl[Symbol.asyncIterator]().next()).value as string;

const main = async () => {
  const [m, n] = (await readline()).split(" ").map(Number);
  const grid = await Promise.all(
    Array.from({ length: m }, async () =>
      (await readline()).split(" ").map(Number)
    )
  );
  const visited = new Array(m)
    .fill(0)
    .map(() => new Array(n).fill(false) as boolean[]);
  const map = new Map<number, number>();
  let index = 1;
  const direction = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  const bfs = (x: number, y: number) => {
    const queue = [[x, y]];
    grid[x][y] = index;
    visited[x][y] = true;
    let res = 1;
    while (queue.length) {
      const [cx, cy] = queue.shift()!;
      for (const [dx, dy] of direction) {
        const nx = cx + dx;
        const ny = cy + dy;
        if (
          nx < 0 ||
          nx >= m ||
          ny < 0 ||
          ny >= n ||
          visited[nx][ny] ||
          grid[nx][ny] === 0
        ) {
          continue;
        }
        queue.push([nx, ny]);
        grid[nx][ny] = index;
        res++;
        visited[nx][ny] = true;
      }
    }
    return res;
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (!visited[i][j] && grid[i][j] !== 0) {
        map.set(index, bfs(i, j));
        index++;
      }
    }
  }
  let res = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 0) {
        let temp = 1;
        for (const [dx, dy] of direction) {
          const nx = dx + i;
          const ny = dy + j;
          if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
            continue;
          }
          if (grid[nx][ny] !== 0) {
            temp += map.get(grid[nx][ny])!;
          }
        }
        res = Math.max(temp, res);
      }
    }
  }
  console.log(res);
  rl.close();
};

main();

[muyulinn]

很高兴经卡尔哥点拨自己写出了这题！

include<bits/stdc++.h>

include

include

using namespace std;

define int long long

define endl '\n'

define INF 0x3f3f3f3f3f3f3f3f

int dir[4][2] = { 0,1,1,0,0,-1,-1,0 }; vector area; int step = 0;

int res = 0;

void dfs(int i, int j, vector<vector>& arr, vector<vector>& vis, unordered_map<int, int>&ma) {

queue<pair<int,int>> que;
que.push({ i,j });

step++;
vis[i][j] = step;

int ssum = 1;

while (!que.empty()) {
    pair<int, int> p = que.front(); que.pop();
    int x = p.first, y = p.second;
    for (int k = 0; k < 4; k++) {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];

        if (nx >= 0 && nx < arr.size() && ny >= 0 && ny < arr[0].size()) {
            if (!vis[nx][ny]&&arr[nx][ny]==1) {
                que.push({ nx,ny });
                vis[nx][ny] = step;
                ssum++;
            }
        }
    }
}
ma[step] = ssum;
res = max(res, ssum);

}

void check(int i, int j, vector<vector>& arr, vector<vector>& vis, unordered_map<int, int>& ma) { // 重要！！！ // 加入判别是否为同一个岛屿 unordered_set s;

int sum = 1;
for (int k = 0; k < 4; k++) {
    int nx = i + dir[k][0];
    int ny = j + dir[k][1];

    if (nx >= 0 && nx < arr.size() && ny >= 0 && ny < arr[0].size()) {
        if (!s.count(vis[nx][ny])) {
            if (vis[nx][ny]) {
                sum += ma[vis[nx][ny]];
                s.insert(vis[nx][ny]);
            }
        }
    }
}
res = max(res, sum);

}

signed main() {

int n, m;
cin >> n >> m;
vector<vector<int>> arr(n, vector<int>(m));
unordered_map<int, int> ma;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> arr[i][j];
    }
}

vector<vector<int>> vis(n, vector<int>(m));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (arr[i][j] == 1 && vis[i][j] == 0) {
            dfs(i, j, arr, vis, ma);
        }
    }
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (arr[i][j] == 0) {
            check(i, j, arr, vis, ma);
        }
    }
}
cout << res << endl;

}