不同路径数（冬季每日一题 4）

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

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

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

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

输入格式
第一行包含三个整数 $n,m,k$。

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

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

数据范围
对于 30% 的数据, $1\le n,m\le 2,0\le k\le 2$
对于 100% 的数据，$1\le n,m\le 5,0\le k\le 5,m\times n>1$
输入样例：

3 3 2
1 1 1
1 1 1
2 1 1
1
2
3
4

输出样例：

5
1

样例解释
一共有 $5$ 种可能的 $3$ 位数：

111
112
121
211
212
1
2
3
4
5

---

#include
#include

using namespace std;

const int N = 10;

int n, m, k;
int g[N][N];
unordered_set<int> S;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int dep, int res){
    
    if(dep == k) S.insert(res);
    else{
        
        for(int i = 0; i < 4; i++){
            
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            dfs(a, b, dep + 1, res * 10 + g[a][b]);
        }
    }
}

int main(){
    
    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            dfs(i, j, 0, g[i][j]);
            
    cout << S.size() << endl;
    
    return 0;
}
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