（吊打二维表中的搜索问题） LeetCode刷题之二维表中进行搜索的问题

简介

在一个二维表中进行搜索是一种经典的题目，最常用的方法就是回溯法，是一种非常直观的方法。我在这篇文章中总结了解这种类型题目的三板斧：

下面我将用两个剑指offer中的例子来进行说明。

13，机器人的运动范围

题目：

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

我们按照上面的三板斧来进行判断，首先看是否需要记录是否访问过当前结点，结果是显然的，不然会重复记录满足要求的位置，再看第二点，也是我觉得官方解题中比较好的点：vector> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
用一个pair数组来保存坐标i,j的移动，我看了真的是觉得非常直观，这样只需要遍历这个数组就能准确控制坐标的移动的四个方向，最后就是弄清楚判定条件：我们移动到一个点首先就是把当前位置的visited置为true，再看是否位数和是小于k的，如果不小于就直接回溯了，如果小于就向四个方向进行移动，需要判断是否超出了边界，是否先前访问过,然后进行递归，同时把记录个数的sum进行++。最后要看在回溯的时候是否有原始变量要进行回退（显然本题不需要，因为不需要记录路径，只需要记录个数）。

tips

在check函数里面调用getsum函数的时候可以 是可以使用完美转发的一个典型条件，但是此时需要转发的数据是一个平凡的数据类型，所以这里是否使用完美转发对性能没有影响。

getsum(forward<int>(i),j
1

解题代码

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited (m,vector<bool>(n,false));
        int sum = 0;
        int i = 0;
        int j = 0;
        check(visited,i,j,k,sum);
        return sum;
    }

    void check(vector<vector<bool>> &visited,int &i, int &j, int k,int &sum){
        if(getsum(i,j) > k){
            return;
        }
        visited[i][j] = true;
        ++sum;
        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for(const auto &dir : directions){
            int newi = i + dir.first, newj = j + dir.second;
            if (newi >= 0 && newi < visited.size() && newj >= 0 && newj < visited[0].size()){
                if (!visited[newi][newj]) {
                    check(visited,newi,newj,k,sum);
                }
            }
        }
    }

    int getsum(int i, int j){
        int sum = 0;
        while(i != 0){
            sum += i%10;
            i /= 10;
        }
        while(j != 0){
            sum += j%10;
            j /= 10;
        }
        return sum; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

12 矩阵中的路径

题目

解题思路

大家可以参考我上面给出的思路，想想这个题目应该怎么解。这个题目在进行移动的时候除了要考虑边界，还要考虑是否访问过，并且判断当前位置是否与给定单词的相应位置的字符一样。

解题代码

class Solution {
public:
    bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {
        if (board[i][j] != s[k]) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        // 表示四个方向 方便进行计算
        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        bool result = false;
        for (const auto& dir: directions) {
            int newi = i + dir.first, newj = j + dir.second;
            if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
                // 判断是否有重复
                if (!visited[newi][newj]) {
                    bool flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        // 回溯
        visited[i][j] = false;
        return result;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size();
        vector<vector<int>> visited(h, vector<int>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                bool flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45