c++ 面试题(1)-----深度优先搜索（DFS）实现

操作系统：ubuntu22.04
IDE:Visual Studio Code
编程语言：C++11

题目描述

地上有一个 m 行 n 列的方格，从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子，但不能进入行坐标和列坐标的数位之和大于 k 的格子。

例如：当 k = 18 时，机器人可以进入方格 [35, 39]（因为 3+5 + 3+9 = 20 > 18，所以不能进入）
问：机器人总共能到达多少个格子？

示例

输入：m=2, n=3, k=1
输出：3

解释：

机器人从 [0,0] 出发，可到达以下格子：

[0,0]
[0,1]
[0,2]

但 [1,0] 的数位和为 1+0=1 ≤ 1，也可以走；
但 [1,1] 的数位和为 1+1=2 > 1，不能进入。

所以总共有 3 个格子可以进入。

解法思路

这是一个典型的搜索类问题，可以用：

深度优先搜索（DFS）
或 广度优先搜索（BFS）

我们只需要从起点 (0, 0) 开始，向四个方向进行递归/遍历，只要满足条件就继续探索，并统计所有能到达的格子。

代码示例

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int movingCount( int m, int n, int k ){vector< vector< bool > > visited( m, vector< bool >( n, false ) );return dfs( 0, 0, m, n, k, visited );}int dfs( int i, int j, int m, int n, int k, vector< vector< bool > >& visited ){// 边界条件判断 or 已访问过 or 不满足数位和条件if ( i < 0 || i >= m || j < 0 || j >= n || visited[ i ][ j ] || bitSum( i ) + bitSum( j ) > k )return 0;visited[ i ][ j ] = true;  // 标记为已访问// 向四个方向探索return 1 + dfs( i + 1, j, m, n, k, visited ) + dfs( i - 1, j, m, n, k, visited ) + dfs( i, j + 1, m, n, k, visited ) + dfs( i, j - 1, m, n, k, visited );}// 计算一个整数的各位数字之和int bitSum( int x ){int sum = 0;while ( x > 0 ){sum += x % 10;x /= 10;}return sum;}
};// 测试代码
int main()
{Solution solution;cout << solution.movingCount( 2, 3, 1 ) << endl;  // 输出: 3cout << solution.movingCount( 3, 3, 0 ) << endl;  // 输出: 1return 0;
}