My JS algorithm climb pit tour – island perimeter

Question 463, the circumference of the island

Address: leetcode-cn.com/problems/is…

If there is a grid in any direction, subtract 2 from the grid in any direction, and then include the opposite direction of the grid.

var islandPerimeter = function(grid) { let res = 0; for(let i = 0; i < grid.length; i++) { for(let j = 0; j < grid[i].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; };Copy the code

A depth-first search method is presented, and the traversal method can be extended to calculate the perimeters of several islands. It should be noted that in order to prevent the land grid from being repeatedly traversed in depth-first search, we need to mark the traversed land grid as already traversed. In the following code, we set the value of 2 as already traversed land grid.

var islandPerimeter = function (grid) {
    const dx = [0, 1, 0, -1];
    const dy = [1, 0, -1, 0];
    const n = grid.length, m = grid[0].length;

    const dfs = (x, y) => {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] === 0) {
            return 1;
        }
        if (grid[x][y] === 2) {
            return 0;
        }
        grid[x][y] = 2;
        let res = 0;
        for (let i = 0; i < 4; ++i) {
            const tx = x + dx[i];
            const ty = y + dy[i];
            res += dfs(tx, ty);
        }
        return res;
    }

    let ans = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (grid[i][j] === 1) {
                ans += dfs(i, j);
            }
        }
    }
    return ans;
};  
Copy the code

However, the time complexity of this method does not decrease, but the space complexity increases.