题目描述

给定一个 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

算法

(暴力搜索) $O(n^k)$

应该是这个复杂度吧。没算过，估计了一下

就所有点都看一遍就好了，我的递归出口是步长到K就让他push到答案里，往前走的时候看一下会不会越界，不过是要去重的，所以用set存一下就就好了

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;

const int N = 6;

int g[N][N];

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

set<vector<int>> res;
vector<int> tmp;


int n, m, k;

void dfs(int x, int y, int step)
{

    if (step == k)
    {
        res.insert(tmp);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m ) {
            tmp.push_back(g[tx][ty]);
            dfs(tx, ty, step + 1);
            tmp.pop_back();
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);

    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++) {
            tmp.push_back(g[i][j]);
            dfs(i, j, 0);
            tmp.clear();
        }
    }

    cout << res.size();
}