(25)Go递归求解二维平面类问题1

问题1：单词搜索 //

树问题，树结构如下

思路如上图：
1）遍历整个二维网格，对二维网格每个元素e，尝试以该元素e开头能否找到相关单词
2）二维数组上的移动借组1个二维数组来完成，x轴为首个元素，y轴为第二个元素，如下：
move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}，上右下左，顺时针移动，
这道题中移动顺序无关紧要，不过有些题目中移动顺序不同会影响性能
如 x=x+move[0][0]，y=y+move[0][1]，为向上移动

具体实现：
func exist(board [][]byte, word string) bool {

    m := len(board) // 行数
    if m == 0 {
        return false
    }
    n := len(board[0])                                // 列数
    move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} // 上右下左,顺时针移动
    // 创建m行n列的visited二维数组,辅助判断元素是否已经被访问过
    visited := newVisited(m, n)

    for x := 0; x < m; x++ {
        for y := 0; y < n; y++ {
            if searchWord(board, word, 0, x, y, m, n, move, visited) {
                return true
            }
        }
    }
    return false
}

// index: word的第几位元素
// 函数功能: 从board[x][y]开始,寻找word[index...len(word)-1]元素
func searchWord(board [][]byte, word string,
    index, x, y, m, n int, move [][]int, visited [][]bool) bool {

    //递归终止条件
    if index == len(word)-1 {
        // 最后元素,返回 board[x][y]==word[index]的结果
        return board[x][y] == word[index]
    } else {
        // 递归过程
        if board[x][y] == word[index] {
            visited[x][y] = true

            // 顺时针移动
            for i := 0; i < 4; i++ {
                newX := x + move[i][0]
                newY := y + move[i][1]
                // (1)x,y不越界;(2)board[x][y]没被访问过;(3)能找到匹配;
                // 前2者同时符合进行下一层搜索,3者同时满足返回true
                if !notArea(newX, newY, m, n) && !visited[newX][newY] &&
                    searchWord(board, word, index+1, newX, newY,
                        m, n, move, visited) {
                    return true
                }
            }
            // 4个方向都找不到,该点重新置为false
            visited[x][y] = false
        }
    }
    return false
}

// 判断是否越界: 越界返回true
func notArea(x, y, m, n int) bool {
    return x < 0 || y < 0 || x >= m || y >= n
}

// 创建m行n列的visited二维数组
func newVisited(m, n int) [][]bool {
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    return visited
}

提交leetcode，通过

问题2：岛屿数量 //

结构如下图，蓝色代表海洋

解决思路和问题1类似，不同的是这里是对陆地进行填充，并返回陆地数量
func numIslands(grid [][]byte) int {
    m := len(grid) // 行数
    if m == 0 {
        return 0
    }

    n := len(grid[0])                                 // 列数
    move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} //顺时针移动
    // 创建m行n列的visited二维数组,辅助判断元素是否已经被访问过
    visited := newVisited(m, n)
    count := 0 // 陆地数量

    for x := 0; x < m; x++ {
        for y := 0; y < n; y++ {
            // 本地不可以写成 == '1',只能写成byte(1),leetcode上则只能写成 == '1'
            // 估计是golang版本不同导致

            // 填充grid[x][y]开头的陆地
            if grid[x][y] == byte(1) {
                if !visited[x][y] {
                    count++
                    dfs(grid, x, y, m, n, move, visited)
                }
            }
        }
    }
    return count
}

// dfs深度优先遍历的简写
// 对包含grid[x][y]的陆地开始,进行floodFill(填充)
func dfs(grid [][]byte, x, y, m, n int, move [][]int, visited [][]bool) {

    visited[x][y] = true
    for i := 0; i < 4; i++ {
        newX := x + move[i][0]
        newY := y + move[i][1]

        //(1)不越界;(2)没被填充过;(3)是陆地;3者同时满足进行下一层搜索
        if !notArea(newX, newY, m, n) && !visited[newX][newY] &&
            grid[newX][newY] == byte(1) {
            dfs(grid, newX, newY, m, n, move, visited)
        }
    }
}

func newVisited(m, n int) [][]bool {
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    return visited
}

func notArea(x, y, m, n int) bool {
    return x < 0 || y < 0 || x >= m || y >= n
}

提交leetcode，通过

继下一篇《(26)Go递归求解n皇后问题》https://www.jianshu.com/p/61beb6faa2b5

有bug欢迎指出