AcWing 3502. 不同路径数
原题链接
简单
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 10;
int n, m, k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int g[N][N];
unordered_set<string> path_set;
void dfs(int x, int y, int length, string state)
{
if (length == k)
{
if (path_set.count(state) != 0)
return;
path_set.insert(state);
return;
}
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) continue;
state.push_back(g[a][b]);
dfs(a, b, length + 1, state);
state.pop_back();
}
}
int main()
{
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 ++)
{
string start = "";
start += g[i][j];
dfs(i, j, 0, start);
}
}
if (k == 0) cout << n * m << endl;
else cout << path_set.size() << endl;
return 0;
}