题目描述
给定一个 n×m 的二维矩阵,其中的每个元素都是一个 [1,9] 之间的正整数。
从矩阵中的任意位置出发,每次可以沿上下左右四个方向前进一步,走过的位置可以重复走。
走了 k 次后,经过的元素会构成一个 (k+1) 位数。
请求出一共可以走出多少个不同的 (k+1) 位数。
样例
输入样例
3 3 2 //n, m, k
1 1 1
1 1 1
2 1 1
输出样例
5 //输出一共有几种不同可能;
数据范围
对于 30% 的数据, 1≤n,m≤2,0≤k≤2
对于 100% 的数据,1≤n,m≤5,0≤k≤5,m×n>1
解题思路
dfs暴搜 $O(n m k)$
此题因为需要走遍所有的情况,没什么好说的,直接暴力搜索,这里使用一个set来存最后的路径结果,可以自动去重;
#include<iostream>
#include<unordered_set>
using namespace std;
int n, m, k;
int matrix[6][6]; //矩阵
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //每一步可能的x和y的方向;
unordered_set<int> ans; //保存路径结果
void dfs(int a, int b, int u, int path){ //u是递归层数,比path的位数少一位;
if(u == k){
ans.insert(path); //边界操作,将路径写入集合;
return;
}
for(int i = 0; i < 4; ++i){
int x = a + dx[i], y = b + dy[i]; //x, y是下一步的位置;
if(x >= 0 && y >= 0 && x < n && y < m) //经过判断,合理的x和y才进行下一步dfs;
dfs(x, y, u+1, path*10 + matrix[x][y]);
}
}
int main()
{
cin>>n>>m>>k;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin>>matrix[i][j];
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
dfs(i, j, 0, matrix[i][j]);
cout<<ans.size()<<endl;
return 0;
}