3502. 不同路径数
本文最后更新于 759 天前,其中的信息可能已经有所发展或是发生改变。

3502. 不同路径数

原题链接

描述

给定一个 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

分析

  • 由于要从不同位置开始遍历,故需要遍历所有的点为搜索的起始点
  • 需要偏移量数组以便进行搜索
  • 题目允许重复走,故不需要考虑回溯
  • 需要记录遍历得到的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;  //记录不同k+1位数的数量

int dx[]={0,0,1,-1},dy[]={1,-1,0,0};  //初始化偏移量数组

void dfs(int l,int r,int u){

    if(u==k+1){  //当位数达到k+1时
        int sum=0;
        for(int i=0;i<k+1;i++){  //遍历当前选择的数,化为k+1位数
            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;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇