本文最后更新于 972 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
描述
给定一个 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
输入样例:
输出样例:
样例解释
一共有 5 种可能的 3 位数:
111
112
121
211
212
分析
- 由于要从不同位置开始遍历,故需要遍历所有的点为搜索的起始点
- 需要偏移量数组以便进行搜索
- 题目允许重复走,故不需要考虑回溯
- 需要记录遍历得到的
k+1
位数,防止重复记录
代码
| #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; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| void dfs(int l,int r,int u){ |
| |
| if(u==k+1){ |
| int sum=0; |
| for(int i=0;i<k+1;i++){ |
| 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; |
| |
| } |