题目描述
给定一个 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
C++ 代码
//求构成的不同数字,开一个哈希表,把所有路径扔进哈希表中,最后输出哈希表的长度就是不同的数字
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
int n,m,k;
int a[10][10];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
unordered_set<int>s;
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 xx=x+dx[i];
int yy=y+dy[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m)
{
dfs(xx,yy,u+1,num*10+a[xx][yy]);
}
}
}}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
dfs(i,j,1,a[i][j]);
}
}
cout<<s.size()<<endl;
}