分析
- 递归回溯出所有情况,将结果插入哈希表中,最终输出哈希表中的元素个数。
代码
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 10;
int n, m, k;
int w[N][N];
unordered_set<int> S;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x, int y, int u, int num) {
if (u > k) S.insert(num);
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)
dfs(a, b, u + 1, num * 10 + w[a][b]);
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> w[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
dfs(i, j, 1, w[i][j]);
cout << S.size() << endl;
return 0;
}