算法题/网格DFS：岛屿的数量

题目

给定一个由岛屿（1表示）和水（0表示）组成的二维网格，请计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或垂直方向上相邻的陆地连接形成。此外，可以假设该网格的四条边均被水包围。

示例1：

输入：grid=[
    ["1","1","1","1","0",],
    ["1","1","0","1","0",],
    ["1","1","0","0","0",],
    ["0","0","0","0","0",],
]
输出：1

示例2：

输入：grid=[
    ["1","1","0","0","0",],
    ["1","1","0","0","0",],
    ["0","0","1","0","0",],
    ["0","0","0","1","1",],
]
输出：3

解答

Java

class Solution {
    private int res;
    public int numIslands(char[][] grid) {
        res = 0;
        //遍历矩阵网格，方便开始其他岛屿的遍历，dfsGrid只具备遍历一格岛屿的能力，不能从一个岛屿跳到另一个岛屿去遍历
        //遍历矩阵就是为了从一个岛屿跳到另一个岛屿去遍历
        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                if (grid[i][j] == '1') {
                    dfsGrid(grid, i, j);
                    res ++;
                }
            }
        }
        return res;
    }

    //dfsGrid的作用是，在上面的循环中调用dfsGrid（给定一个初始坐标），然后dfsGrid从这个初始坐标开始遍历，
    //标记与这个初始坐标直接或间接相邻的陆地，这些陆地组成一个岛屿
    private void dfsGrid(char[][] grid, int row, int col) {
        //判断坐标是否(row,col)是否在网格中，如果不在则返回
        if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0) {
            return;
        }

        if (grid[row][col] != '1') {
            return;
        }

        grid[row][col] = '2';//将格子标记为已经遍历过
    
        dfsGrid(grid, row - 1, col);
        dfsGrid(grid, row + 1, col);
        dfsGrid(grid, row, col - 1);
        dfsGrid(grid, row, col + 1);
    }
}

JavaScript

class Solution {
    constructor() {
        this.res = 0;
    }

    numIslands(grid) {
        this.res = 0;
        for (let i = 0; i < grid.length; i++) {
            for (let j = 0; j < grid[0].length; j++) {
                if (grid[i][j] === '1') {
                    this.dfsGrid(grid, i, j);
                    this.res++;
                }
            }
        }
        return this.res;
    }

    dfsGrid(grid, row, col) {
        if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0) {
            return;
        }

        if (grid[row][col] !== '1') {
            return;
        }

        grid[row][col] = '2';

        this.dfsGrid(grid, row - 1, col);
        this.dfsGrid(grid, row + 1, col);
        this.dfsGrid(grid, row, col - 1);
        this.dfsGrid(grid, row, col + 1);
    }
}

Python

class Solution:
    def __init__(self):
        self.res = 0

    def numIslands(self, grid):
        self.res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfsGrid(grid, i, j)
                    self.res += 1
        return self.res

    def dfsGrid(self, grid, row, col):
        if row >= len(grid) or col >= len(grid[0]) or row < 0 or col < 0:
            return

        if grid[row][col] != '1':
            return

        grid[row][col] = '2'

        self.dfsGrid(grid, row - 1, col)
        self.dfsGrid(grid, row + 1, col)
        self.dfsGrid(grid, row, col - 1)
        self.dfsGrid(grid, row, col + 1)

Go

type Solution struct {
	res int
}

func NewSolution() *Solution {
	return &Solution{}
}

func (s *Solution) numIslands(grid [][]byte) int {
	s.res = 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				s.dfsGrid(grid, i, j)
				s.res++
			}
		}
	}
	return s.res
}

func (s *Solution) dfsGrid(grid [][]byte, row, col int) {
	if row >= len(grid) || col >= len(grid[0]) || row < 0 || col < 0 {
		return
	}

	if grid[row][col] != '1' {
		return
	}

	grid[row][col] = '2'

	s.dfsGrid(grid, row-1, col)
	s.dfsGrid(grid, row+1, col)
	s.dfsGrid(grid, row, col-1)
	s.dfsGrid(grid, row, col+1)
}