463. Island Perimeter

Description

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
Example 2:

Example 2:

Input: grid = [[1]]
Output: 4
Example 3:

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid.

思路

先用一層 for 迴圈遍歷所有的 grid，遍歷的過程每一格使用 DFS 去找所有是 1 的格子，並將它清為 0。

You are given row x col grid representing a map where

這代表它會給我們 row, col 這兩個參數嗎? 他不會給，要自己設

又因為它需要計算的是邊長，所以我改為 grid 清為 2，然後如果有重疊的邊長會附蓋掉，所以設定數個針對相鄰個子的判別式將覆蓋掉的邊常扣掉。

C++

寫得很丑…然後發現其實不用 DFS 就可以解。

class Solution {
public:
    int count = 0;
    void dfs(vector<vector<int>>& grid, int rrow, int ccol, int maxr,
             int maxc) {
        if (rrow < 0 || ccol < 0 || rrow >= maxr || ccol >= maxc ||
            !grid[rrow][ccol] || grid[rrow][ccol] == 2)
            return;

        grid[rrow][ccol] = 2;
        count+=4;
        if (rrow - 1 >= 0 && grid[rrow - 1][ccol] == 2)
            count -= 2;
        if (rrow + 1 < maxr && grid[rrow + 1][ccol] == 2)
            count -= 2;
        if (ccol - 1 >= 0 && grid[rrow][ccol - 1] == 2)
            count -= 2;
        if (ccol + 1 < maxc && grid[rrow][ccol + 1] == 2)
            count -= 2;
        dfs(grid, rrow - 1, ccol, maxr, maxc);
        dfs(grid, rrow + 1, ccol, maxr, maxc);
        dfs(grid, rrow, ccol - 1, maxr, maxc);
        dfs(grid, rrow, ccol + 1, maxr, maxc);
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        int maxrow = grid.size();
        int maxcol = grid[0].size();
        for (int i = 0; i < maxrow; i++) {
            for (int j = 0; j < maxcol; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, maxrow, maxcol);
                    return count;
                }
            }
        }
        return count;
    }
};

另解

判斷每一格的上下左右鄰居，若有水則 +1 ，另外如果為邊界也同樣 +1

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int ans = 0;
        for(int i=0; i<grid.size(); i++) {
            for(int j=0; j<grid[0].size(); j++) {
                if(grid[i][j] == 1) {
                    // cell at the boundries
                    if(i == 0) ans++;
                    if(j == 0) ans++;
                    if(i == grid.size()-1) ans++;
                    if(j == grid[0].size()-1) ans++;

                    // check neighboor
                    if(i > 0 && grid[i-1][j] == 0) ans++;
                    if(j > 0 && grid[i][j-1] == 0) ans++;
                    if(i < grid.size()-1 && grid[i+1][j] == 0) ans++;
                    if(j < grid[0].size()-1 && grid[i][j+1] == 0) ans++;
                }
            }
        }
        return ans;
    }
};