LeetCode 827. Making A Large Island

https://leetcode.com/problems/making-a-large-island/description/

題目大意

給定

$n\times n$ 的二元矩陣 gird ，最多可以將裡面一個 0 翻轉成 1
1 所連成的區域為島嶼 ，這個連法只能上下左右，無法斜著對角連線

回傳經過操作後，grid 最大的島嶼面積？

---

Constraints:

• $\mathrm{grid}.\mathrm{length}=n$
• $\mathrm{grid}[i].\mathrm{length}=n$
• $1\le n\le 500$
• $\mathrm{grid}[i][j]=0\text{ or }1$

思考

想當然，我們可以用 DFS or BFS 來遍歷這張圖
因為元素只會是 0 or 1 ，所以我們可以用比 1 大的值作為標記來劃分圖上不同的島嶼

接著，我們就把每個 0 都試著變成 1 看看跟它周圍的島嶼連接後的大小如何

C++ 參考解答

class Solution
{
public:
    int largestIsland(vector<vector<int>> &grid)
    {
        const int n = grid.size();
        vector<int> islandSize;
        islandSize.reserve(n * n);
        int label = 2, ans = 0;

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    islandSize.push_back(dfs(grid, i, j, label++));
                    ans = max(ans, islandSize.back());
                }
            }
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 0)
                    ans = max(ans, connectIslands(grid, islandSize, i, j));
            }
        }

        return ans;
    }

private:
    static constexpr array<array<int, 2>, 4> directions = {{
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0},
    }};

    bool isBounded(int ordX, int ordY, int n) noexcept
    {
        return ordX >= 0 && ordY >= 0 && ordX < n && ordY < n;
    }

    int dfs(vector<vector<int>> &grid, int x, int y, int label)
    {
        const int n = grid.size();
        grid[x][y] = label;
        int size = 1;

        for (const auto direction : directions)
        {
            const int ordX = x + direction[0];
            const int ordY = y + direction[1];

            if (isBounded(ordX, ordY, n) && grid[ordX][ordY] == 1)
                size += dfs(grid, ordX, ordY, label);
        }

        return size;
    }

    int connectIslands(vector<vector<int>> &grid, vector<int> &islandSize, int x, int y)
    {
        const int n = grid.size();
        int visited[4] = {0};
        int newSize = 1, directIdx = 0;

        for (const auto direction : directions)
        {
            const int ordX = x + direction[0];
            const int ordY = y + direction[1];
            if (!isBounded(ordX, ordY, n))
                continue;

            const int label = grid[ordX][ordY];
            if (label > 1)
            {
                bool found = false;

                for (int i = 0; i < directIdx; ++i)
                {
                    if (visited[i] == label)
                    {
                        found = true;
                        break;
                    }
                }

                if (!found)
                {
                    visited[directIdx++] = label;
                    newSize += islandSize[label - 2];
                }
            }
        }

        return newSize;
    }
};

Go 參考解答

func largestIsland(grid [][]int) int {
	n := len(grid)
	islandSize := make([]int, n*n)
	label, ans := 2, 0

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				size := dfs(grid, i, j, label)
				islandSize[label-2] = size
				ans = max(ans, size)
				label++
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				ans = max(ans, connectIslands(grid, islandSize, i, j))
			}
		}
	}

	return ans
}

var directions = [4][2]int{
	{0, 1}, {1, 0}, {0, -1}, {-1, 0},
}

func isBounded(x, y, n int) bool {
	return x >= 0 && y >= 0 && x < n && y < n
}

func dfs(grid [][]int, x, y, label int) int {
	n := len(grid)
	grid[x][y] = label
	size := 1

	for _, direction := range directions {
		ordX, ordY := x+direction[0], y+direction[1]
		if isBounded(ordX, ordY, n) && grid[ordX][ordY] == 1 {
			size += dfs(grid, ordX, ordY, label)
		}
	}

	return size
}

func connectIslands(grid [][]int, islandSize []int, x, y int) int {
	n := len(grid)
	visited := [4]int{0, 0, 0, 0}
	newSize, idx := 1, 0

	for _, direction := range directions {
		ordX, ordY := x+direction[0], y+direction[1]
		if isBounded(ordX, ordY, n) {
			label := grid[ordX][ordY]
			if label > 1 {
				found := false
				for i := 0; i < idx; i++ {
					if visited[i] == label {
						found = true
						break
					}
				}

				if !found {
					visited[idx] = label
					idx++
					newSize += islandSize[label-2]
				}
			}
		}
	}

	return newSize
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}