今天190位同学拿到offer
算基础课 842(dfs) )
844(bfs) 的练习题吧
bfs dfs皆可
大体思路就是枚举矩阵每一个位置的每种可能路径值 存set里
最后set内元素数量就是答案

法1 $dfs$

#include <iostream>
#include <queue>
#include <unordered_set>
#include <cmath>
using namespace std;
#define f first
#define s second
//bfs dfs皆可
//大体思路就是枚举矩阵每一个位置的每种可能路径值 存set里 
//最后set内元素数量就是答案
int n,k,m;
int w[10][10];//w存矩阵
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};//偏移量
unordered_set <int> st;
void dfs(int u,int x,int y,int z){
//u表当前递归层数 x,y为当前坐标 z是当前的路径数值    
    if (u==k+1) {
        st.insert(z);
//步数走到了 存入set        
        return ;
    }
    else{
        for (int i=0;i<4;i++){
//上下左右嘛 枚举偏移量            
            int tx=x+dx[i],ty=y+dy[i];
            if (tx>=0&&ty>=0&&tx<n&&ty<m){
                dfs(u+1,tx,ty,z*10+w[tx][ty]);
//进入下一层 u+1                 
            }
            else continue;
        }
    }
}
int main (){
    scanf ("%d%d%d",&n,&m,&k);
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>w[i][j];
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
//枚举矩阵每一个位置的每种可能            
            dfs(1,i,j,w[i][j]);
        }
    }
    cout<<st.size()<<'\n';
    return 0;
}

法2 $bfs$

#include <iostream>
#include <queue>
#include <unordered_set>
#include <cmath>
using namespace std;
#define f first
#define s second
//#define  标识符  常量   //注意, 最后没有分号
//bfs dfs皆可
//大体思路就是枚举矩阵每一个位置的每种可能路径值 存set里 
//最后set内元素数量就是答案
int n,k,m;
int w[10][10];//w存矩阵
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};//偏移量
unordered_set <int> st;
void bfs(int x,int y){
    queue <pair<pair<int  ,int  >,   int > > q;
//             {    {x坐标,y坐标}, 路径值}    
    q.push({{x,y},w[x][y]});
    while (q.size()){
        auto t=q.front();
//上下等价        
        //pair<pair<int,int >,int >t=q.front();
        q.pop();
//记得删除哦 不然超时        
        for (int i=0;i<4;i++){
            int tx=t.f.f+dx[i],ty=t.f.s+dy[i];
// #define f first
// #define s second
//因为在6，7行进行了上述宏定义所以 不用打first second
//使用方法#define  标识符  常量   //注意, 最后没有分号
            if (tx>=0&&tx<n&&ty>=0&&ty<m){
                if ((t.s*10+w[tx][ty])>pow(10,k)){
//走k步路径值是k+1位数 值域为(10^k,10^(k+1))
                    //if (!st.count(t.s*10+w[tx][ty])) cout<<t.s*10+w[tx][ty]<<' ';
                    st.insert(t.s*10+w[tx][ty]);
                }
                else q.push({{tx,ty},t.s*10+w[tx][ty]});
//          q.push( {    {    tx    ,    ty  },t.s*10+w[tx][ty]}  );                
            //      {    {可走x坐标,可走y坐标},  走后路径值    } 
            }
        }
    }
}
int main (){
    scanf ("%d%d%d",&n,&m,&k);
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>w[i][j];
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
//枚举矩阵每一个位置的每种可能
            bfs(i,j);
        }
    }
    cout<<st.size()<<'\n';
    return 0;
}