题目描述
给定一个 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
算法1
(暴力枚举) $O(n^2)$
数据量非常小。直接dfs
时间复杂度
参考文献
python3 代码
[n, m, k] = [int(x) for x in input().split()]
nums = [[] for _ in range(n)]
for i in range(n):
nums[i] = [int(x) for x in input().split()]
res = set()
def dfs(r, c, step, path):
path += str(nums[r][c])
if step == k:
res.add(path[:])
return
for nr, nc in ((r-1, c), (r+1,c), (r, c-1), (r,c+1)):
if 0 <= nr < n and 0 <= nc < m:
dfs(nr, nc, step + 1, path)
for r in range(n):
for c in range(m):
dfs(r, c, 0, "")
print(len(res))
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
int m; cin >> m;
int k; cin >> k;
vector<vector<int>> nums(n, vector<int>(m, 0));
for (int r = 0; r < n; r ++)
for (int c = 0; c < m; c ++)
cin >> nums[r][c];
unordered_set<string> res;
std::function<void(int,int,int,string)> dfs = [&] (int r, int c, int step, string path)
{
path += ('0' + nums[r][c]);
if (step == k)
{
res.insert(path);
return;
}
for (auto [nr, nc] : vector<pair<int,int>>{{r-1, c}, {r+1, c}, {r,c-1}, {r,c+1}})
{
if (0 <= nr && nr < n && 0 <= nc && nc < m)
{
dfs(nr, nc, step + 1, path);
}
}
};
for (int r = 0; r < n; r ++)
for (int c = 0; c < m; c ++)
dfs(r, c, 0, "");
cout << res.size() << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla