题目

不同路径数

给定一个 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中存放当前步数u,答案 res,重点是记得有个to_string()库函数

二、实现

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 10;
int g[N][N];
map<string,int> mp;
int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
int n,m,k;
void dfs(int x,int y,string res, int u)
{
if(u == k)
{
mp[res] ++;
return;
}
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
dfs(nx,ny,res + to_string(g[nx][ny]) ,u + 1);
}
}
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 res =to_string(g[i][j]);
dfs(i,j,res,0);
}
cout<<mp.size();
}

最后

以上就是怕孤独绿草为你收集整理的不同路径数题目一、主要思路二、实现的全部内容，希望文章能够帮你解决不同路径数题目一、主要思路二、实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。