题目描述
给定一个 n×m 的二维矩阵,其中的每个元素都是一个 [1,9] 之间的正整数。
从矩阵中的任意位置出发,每次可以沿上下左右四个方向前进一步,走过的位置可以重复走。
走了 k 次后,经过的元素会构成一个 (k+1) 位数。
请求出一共可以走出多少个不同的 (k+1) 位数。
输入样例
3 3 2
1 1 1
1 1 1
2 1 1
输出样例
5
算法1
暴力dfs遍历所有可能性
由于这道题的数据范围很小,可以考虑直接暴搜出所有可能的结果,由于k不会超过5,因此直接使用int暂存每次结果
这样比较当前数在之前是否出现过只需要O(1)的复杂度
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <queue>
using namespace std;
//注意到数据范围这道题就是简单的dfs爆搜遍历 而不是其他的 直接使用unorder统计一下出现的数字 记得恢复现场
const int N = 10;
int g[N][N];
unordered_set<int> st; //统计有没有在之前出现过
int res = 0;
int n,m,k;
int num = 0; // 暂存dfs每次得到的数字 记得还原现场
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
void dfs(int x,int y,int layer)
{
if(layer == k)
{
//递归终止
if (!st.count(num))
{
// cout << num << endl;
res++;
st.insert(num);
}
return;
}
//遍历一下所有可以走到的点
for(int d = 0 ; d < 4 ;d ++)
{
int new_x = x + dx[d], new_y = y+dy[d];
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)
{
num = num * 10 + g[new_x][new_y];
dfs(new_x,new_y,layer+1);
num = num / 10; //还原现场
}
}
}
int main()
{
cin >> n >> m >>k;
//读入数据
for(int i =0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> g[i][j];
}
}
// 遍历所有dfs的起点
for(int i = 0; i < n; i++)
{
for(int j = 0; j <m; j++)
{
num = g[i][j];
dfs(i,j,0);
}
}
cout << res <<endl;
return 0;
}