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
输入样例：
3 3 2
1 1 1
1 1 1
2 1 1
输出样例：
5
样例解释
一共有 5 种可能的 3 位数：

111
112
121
211
212

#include<bits/stdc++.h>
using namespace std;
int m, n, k;
set<string> s;
//int visited[10] = { 0 };
int d[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
void dfs(vector<vector<int>> &grid,int x,int y,string str){
if (str.size() == k+1) {
s.insert(str);
return;
}
for (int i = 0; i < 4; i++) {
int new_x = x + d[i][0];
int new_y = y + d[i][1];
if (new_x >= 0 && new_x < m&&new_y >= 0 && new_y < n) {
str += to_string(grid[new_x][new_y]);
dfs(grid, new_x, new_y, str);
str.pop_back();
}
}
}
int main() {
cin >> m >> n >> k;
vector<vector<int>> grid(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(grid,i, j, to_string(grid[i][j]));
}
}
//dfs(grid, 2, 0, to_string(grid[2][0]));
//std::set<std::string>::iterator it = s.begin();
//while (it != s.end())
//{
//	// Print the element
//	std::cout << (*it) << " , ";
//	//Increment the iterator
//	it++;
//}
cout << s.size() << endl;
return 0;
}

最后

以上就是真实犀牛为你收集整理的3502. 不同路径数的全部内容，希望文章能够帮你解决3502. 不同路径数所遇到的程序开发问题。

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