【LeetCode】463.Island Perimeter解題報告(Python)

作者:負雪明ろうそくid:fuxuemingzhu個人ブログ:http://fuxuemingzhu.cn/
目次

タイトル説明

テーマ大意

解題方法

交差部

を減算.

参考資料

日付

タイトルアドレス: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:

Input:
[[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 below:

テーマの大意
2次元配列で表される地図を与え,ある位置が1であれば陸地,位置が0で海洋を表す.陸地がつながっていると小さな島を構成することが知られており、この地図には小さな島が1つしかありません.小島の周長を求めます.
解題方法
交差を減算
直接解くのは難しいようで、1つの簡単な方法を使うことができます:各位置の周長は4で、もし別の陸地とつながっているならば、この2つの陸地の周長とマイナス2.だから島全体の周長は4です×陸地数-2×交差数.

class Solution:
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        M, N = len(grid), len(grid[0])
        counts = 0
        neighbors = 0
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 1:
                    counts += 1
                    if i < M - 1:
                        if grid[i + 1][j] == 1:
                            neighbors += 1
                    if j < N - 1:
                        if grid[i][j + 1] == 1:
                            neighbors += 1
        return 4 * counts - 2 * neighbors

参考資料
https://leetcode.com/problems/island-perimeter/discuss/95001/clear-and-easy-java-solution
日付
2018年11月8日——プロジェクトの進展が遅い