本文最后更新于 443 天前，其中的信息可能已经有所发展或是发生改变。
3502. 不同路径数
原题链接
描述
给定一个 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 输入样例：
代码语言：javascript复制3 3 2
1 1 1
1 1 1
2 1 1输出样例：
代码语言：javascript复制5样例解释 一共有 5 种可能的 3 位数： 111 112 121 211 212
分析
- 由于要从不同位置开始遍历，故需要遍历所有的点为搜索的起始点
- 需要偏移量数组以便进行搜索
- 题目允许重复走，故不需要考虑回溯
- 需要记录遍历得到的
k 1位数，防止重复记录
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int N=10;
const int M=1e6 3;
int mp[N][N]; //存储数据
int res[N]; //存储当前选择到的数
bool vis[M]; //标记是否出现过该数
int n,m,k;
int ans; //记录不同k 1位数的数量
int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; //初始化偏移量数组
void dfs(int l,int r,int u){
if(u==k 1){ //当位数达到k 1时
int sum=0;
for(int i=0;i<k 1;i ){ //遍历当前选择的数，化为k 1位数
sum=sum*10 res[i];
}
if(!vis[sum]){ //若该数未曾出现过
vis[sum]=1; //标记为出现过
ans ; //记录数量
}
return ;
}
for(int i=0;i<4;i ){ //循环遍历偏移量数组
int x=l dx[i],y=r dy[i];
if(x>=0&&x<n&&y>=0&&y<m){ //判断该点是否在范围内，可以重复走过
res[u]=mp[x][y]; //选择该点
dfs(x,y,u 1); //递归到下一层
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i ){
for(int j=0;j<m;j ){
cin>>mp[i][j];
}
}
for(int i=0;i<n;i ){
for(int j=0;j<m;j ){
dfs(i,j,0); //遍历所有的点作为搜索的起始点
}
}
cout<<ans<<endl;
return 0;
}
