算法:暴力搜索
时间复杂度: $O(N \times M \times 4^K)$
对 $M \times N$ 的每个位置枚举可能路径,用哈希表对得到的路径去重即可。
找工作加油!
C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 10;
int n, m, k;
int g[N][N];
unordered_map<int, int> mp;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void dfs(int sx, int sy, int k, int num)
{
if (k == 0) {
if (mp.count(num) == 0) mp[num] = 1;
return ;
}
for (int i = 0; i < 4; ++i) {
int x = sx + dx[i], y = sy + dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= m) {
dfs(x, y, k - 1, num * 10 + g[x][y]);
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dfs(i, j, k, g[i][j]);
}
}
int res = 0;
for (auto& [x, c] : mp) ++res;
cout << res << endl;
return 0;
}