蓝桥杯每日一题：不同路径数（dfs深度优先）

给定一个 n×m的二维矩阵，其中的每个元素都是一个 [1,9] 之间的正整数。

从矩阵中的任意位置出发，每次可以沿上下左右四个方向前进一步，走过的位置可以重复走。

走了 k 次后，经过的元素会构成一个 (k+1) 位数。

请求出一共可以走出多少个不同的 (k+1) 位数。

输入格式

第一行包含三个整数 n,m,k。

接下来 n 行，每行包含 m 个空格隔开的整数，表示给定矩阵。

输出格式

输出一个整数，表示可以走出的不同 (k+1) 位数的个数。

数据范围

对于 30% 的数据, 1≤n,m≤2,0≤k≤2
对于 100% 的数据，1≤n,m≤5,0≤k≤5,m×n>1

输入样例：

3 3 2
1 1 1
1 1 1
2 1 1

输出样例：

5

样例解释

一共有 5 种可能的 3 位数：

111
112
121
211
212

 这题用到深度优先搜索，搜索k次，判断组成的k+1位数是否出现过，未出现过则答案+1.

判重可以用哈希的方式，用一个res存储这个k+1位数

下面看代码详解

 

 这样就AC啦