463. Island Perimeter

https://leetcode.com/problems/island-perimeter/description/

You are given a map in form of a two-dimensional integer grid where 1 represents land and 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" (water inside that 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:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16

Thoughts

由01构成的矩阵，问1所组成的图形的周长。从左上角依次遍历，当是1先加四条边，再检查右边/下边是否为1，是就减2，把这两个块增加的两条边删去。

Code

/*
 * @lc app=leetcode id=463 lang=cpp
 *
 * [463] Island Perimeter
 */

// @lc code=start
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        const int M = grid.size(), N = M == 0 ? 0 : grid[0].size();
        int res = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 0) continue;
                res += 4;
                if (i < M - 1 && grid[i + 1][j] == 1) res -= 2;
                if (j < N - 1 && grid[i][j + 1] == 1) res -= 2;
            }
        } 
        return res;
    }
};
// @lc code=end

class Solution {
    public int islandPerimeter(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    res += 4;
                    if (i > 0 && grid[i - 1][j] == 1) {
                        res -= 2;
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        res -= 2;
                    }
                }
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(MN).