一、题目描述：
给定一个矩阵的行和列row，col，以及阈值sho，从起点(0,0)出发，每次可以往上、下、左、右四个方向走，并且走到(i,j)时，i和j的每位数之和需要小于等于sho，问最多可以走多少格子。
二、官方题解（DFS解法）：
我们假设一个5x5矩阵，阈值sho=3，如果我们用DFS的话，就相当于“不撞南墙不回头”，我在下面画了一个图，
最开始，我们在(0,0)的位置，我们假设按照{右，下，左，上}的方向去试探。所以我们走的顺序应该是按照图中的下标走的。 当走到4的时候，发现不能继续往右边走，并且4个方向都走不通了，那就回溯到3,发现可以走到5，接着就站在5的视角，发现可以走6，就一直按照这个想法。
本题的递归函数就是：首先站在(0,0)的视角，先往右试探，发现可以走，就以下一个为视角，继续做相同的事情。
递归函数模板为：
dfs(){ // 第一步，检查下标 // 第二步：检查是否被访问过，或者是否满足当前匹配条件 // 第三步：检查是否满足返回结果条件 // 第四步：都没有返回，说明应该进行下一步递归 // 标记 dfs(下一次) // 回溯 } int main() { dfs(0, 0); }按照模板改写代码：
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<iomanip> using namespace std; class Solution { public: using V = vector<int>; using VV = vector<V>; int dir[5] = { -1, 0, 1, 0, -1 };//控制机器人运动方向的权值 int check(int n) { //计算数n的每位数之和。题目描述中是i,j的每位数之和，不是i和j之和 int sum = 0; while (n) { sum += (n % 10); n /= 10; } return sum; } void dfs(int x, int y, int sho, int r, int c, int &ret, VV &mark) { // 检查下标 和 是否访问 if (x < 0 || x >= r || y < 0 || y >= c || mark[x][y] == 1) { return; } // 检查当前坐标是否满足条件 if (check(x) + check(y) > sho) { return; } // 代码走到这里，说明当前坐标符合条件 mark[x][y] = 1; ret += 1; for (int i = 0; i < 4; ++i) {//按[上、右、下、左]的顺序 dfs(x + dir[i], y + dir[i + 1], sho, r, c, ret, mark);//递归 } } int movingCount(int sho, int rows, int cols) { if (sho <= 0) { return 0; } VV mark(rows, V(cols, -1)); /* //向屏幕输出mark元素 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { cout << setw(5) << mark[i][j] << setw(5); } cout << endl; }*/ int ret = 0; dfs(0, 0, sho, rows, cols, ret, mark); return ret; } }; int main() { Solution obj; obj.movingCount(4,5,5); return 0; }【代码中关于vector和vector<vector<int>>的高级用法】
