3502-不同路径数

3502. 不同路径数

原题链接

描述

给定一个 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+1 位数，防止重复记录

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
const int M = 1e6 + 3;

int mp[N][N];  // 存储数据
int res[N];    // 存储当前选择到的数
bool vis[M];   // 标记是否出现过该数
int n, m, k;
int ans;       // 记录不同 k+1 位数的数量
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};  // 初始化偏移量数组

void dfs(int l, int r, int u) {
    if (u == k + 1) {  // 当位数达到 k+1 时
        int sum = 0;
        for (int i = 0; i < k + 1; i++) {  // 遍历当前选择的数，化为 k+1 位数
            sum = sum * 10 + res[i];
        }
        if (!vis[sum]) {  // 若该数未曾出现过
            vis[sum] = 1;  // 标记为出现过
            ans++;         // 记录数量
        }
        return;
    }
    for (int i = 0; i < 4; i++) {  // 循环遍历偏移量数组
        int x = l + dx[i], y = r + dy[i];
        if (x >= 0 && x < n && y >= 0 && y < m) {  // 判断该点是否在范围内，可以重复走过
            res[u] = mp[x][y];  // 选择该点
            dfs(x, y, u + 1);   // 递归到下一层
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res[0] = mp[i][j];
            dfs(i, j, 1);
        }
    }
    cout << ans << endl;
    return 0;
}