A Daily Topic # 4
不同路径数
给定一个 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
+++
思路:数据量小,直接dfs一下每个点的所有可能情况即可,然后利用set的去重特性求出方案数。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 7;
int a[N][N];
int n, m, k;
set<int> s;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int i, int j, int cnt, int num)
{
if (cnt >= k + 1)
{
s.insert(num);
return;
}
for (int t = 0; t < 4; t ++ )
{
int x = i + dx[t], y = j + dy[t];//偏移量
if (x >= 1 && x <= n && y >= 1 && y <= m)
{
dfs(x, y, cnt + 1, num * 10 + a[x][y]);
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> a[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
dfs(i, j, 1, a[i][j]);
cout << s.size() << endl;
return 0;
}