一、題目

1、原題鏈接

3502. 不同路徑數(shù)

2、題目描述

給定一個 n×m 的二維矩陣，其中的每個元素都是一個 [1,9] 之間的正整數(shù)。

從矩陣中的任意位置出發(fā)，每次可以沿上下左右四個方向前進一步，走過的位置可以重復走。

走了 k 次后，經(jīng)過的元素會構成一個 (k+1) 位數(shù)。

請求出 一共可以走出多少個不同的 (k+1) 位數(shù)。

輸入格式

第一行包含三個整數(shù) n,m,k。

接下來 n 行，每行包含 m 個空格隔開的整數(shù)，表示給定矩陣。

輸出格式

輸出一個整數(shù)，表示可以走出的不同 (k+1) 位數(shù)的個數(shù)。

數(shù)據(jù)范圍

對于 30% 的數(shù)據(jù), 1≤n,m≤2,0≤k≤2

對于 100% 的數(shù)據(jù)，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 位數(shù)：

111
112
121
211
212

二、解題報告

1、思路分析

思路來源：y總講解視頻
y總yyds

（1）因為走過的位置可以重復走，所以針對每個點，它四個方向且在范圍中的點都可以走。
（2）利用dfs對每個點可能構成的（k+1）位數(shù)進行搜索，然后將構成的數(shù)加入哈希表中去重，最終哈希表中元素的數(shù)量，即為不同的（k+1）位數(shù)的個數(shù)。
（3）模擬上述過程，輸出答案，即為所求。

2、時間復雜度

時間復雜度為O(n* m *4^k)

3、代碼詳解

#include <iostream>
#include <unordered_set>
using namespace std;
const int N=10;
int g[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};     //記錄上下左右四個方向的坐標偏移量
int n,m,k;
unordered_set<int> se;                  //記錄不同數(shù)字的個數(shù)
void dfs(int x,int y,int u,int sum){     //(x,y)為坐標，u代表當前是第幾位數(shù)（0~k）,sum代表當前數(shù)字組成的數(shù)的值if(u==k){                            //如果已經(jīng)有k個數(shù)字，結束，收獲答案加入哈希表中，并回溯se.insert(sum);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){       //如果走到的點在范圍中，繼續(xù)向下搜索dfs(a,b,u+1,sum*10+g[a][b]); }}
}
int main(){cin>>n>>m>>k;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(i,j,0,g[i][j]);}}cout<<se.size();return 0;
}

三、知識風暴

深搜DFS

• 盡量縱深搜索，可以利用?；蜻f歸實現(xiàn)。