题目描述
给定一个 $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
算法1
(DFS)
- 数据范围最大为
5
,因此可以直接暴搜所有方案 - 枚举每个点作为起点进行上下左右四个方向的搜索,搜索了
k
步之后就可以返回,最后用set
进行去重即可
Java 代码
import java.util.*;
public class Main{
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] g = new int[10][10];
static Set<Integer> set = new HashSet<>();
static int n, m, k;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
g[i][j] = sc.nextInt();
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dfs(i, j, 0, g[i][j]);
}
}
System.out.println(set.size());
}
static void dfs(int x, int y, int cnt, int cur){
if(cnt == k){
set.add(cur);
return;
}
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m){
dfs(a, b, cnt + 1, cur * 10 + g[a][b]);
}
}
}
}