Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Why DFS

I believe that the friends who have learned data structure know that DFS (depth-first search) is a very important search algorithm, may directly say that you feel not conditional you can go to see some algorithm competition. Every one of these games is going to involve DFS in some way or another, and DFS is probably something we all know about but we all know about it in order to avoid being too arrogant to write about it. In order to avoid this embarrassment we are going to take advantage of this activity for a few days to practice, well we don’t have to talk about fat.

PS: THESE days, I found that some fat friends do not know what DFS is. I’d better say it briefly, otherwise this problem will be difficult to do.

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

For example, if we initiate A depth-first search from point A (the following access order is not unique, the second point could be either B or C or D), we might get an access process like A->B->E (no path! Backtrace to A)->C->F->H->G->D (no path, finally backtrace to A,A also has no adjacent node not visited, the search ends). The characteristic of depth-first search is briefly explained: the result of depth-first search must be a connected component of graph. Depth-first searches can be initiated from multiple points. If you sort each node by “end time” during a depth-first search (by creating a list, then adding that node to the end of the list if all of its neighbors have been accessed, and then reversing the entire list), Then we can get what is called “topological sort “, i.e. topological sort. [1]

The title

Grid [I][j] = 1 represents land, and grid[I][j] = 0 represents water.

The cells in the grid are connected horizontally and vertically (not diagonally). The grid is completely surrounded by water, but there happens to be one island (or one or more islands connected by grids representing land).

There is no “lake” (” lake “means the water is inside the island and not connected to the water around the island). A cell is a square with sides of length 1. The grid is rectangular and not more than 100 in width or height. Calculate the circumference of the island.

Example 1:

Input: grid = [[0.1.0.0], [1.1.1.0], [0.1.0.0], [1.1.0.0]] output:16Explanation: Its circumference is shown in the picture above16It has a yellow edgeCopy the code

The sample2Input: grid = [[1]] output:4
Copy the code

The sample3Input: grid = [[1.0]] output:4
Copy the code

Iteration is the best way to iterate, so why include it in DFS? I thought I’d show you how DFS works in this kind of problem.

Solution a: DFS

public int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                // There is only one island in the list
                returndfs(grid, r, c); }}}return 0;
}

int dfs(int[][] grid, int r, int c) {
    if(! (0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {// Handle the case where the grid is on the edge
        return 1;
    }
    if (grid[r][c] == 0) {
        return 1;
    }
    if(grid[r][c] ! =1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)/ Basic DFS framework: search four adjacent squares at a time + DFS (grid, r +)1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}


Copy the code

Solution 2: Iteration is easier

For each side of a land grid, it counts as the perimeter of the island if and only if that side is the boundary of the grid or if the adjacent cell is water. Thus, we can traverse each land grid to see if its four directions are boundaries or waters, and if so, add the contribution of this edge (i.e. 11) to the answer \textit{ans}ans.

class Solution {
    static int[] dx = {0.1.0, -1};// Use to judge around (the result is up, down, left, right)
    static int[] dy = {1.0, -1.0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; ++k) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            cnt += 1; } } ans += cnt; }}}returnans; }}Copy the code