A Daily Topic # 4 不同路径数(DFS)

A Daily Topic # 4

不同路径数

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

+++

思路:数据量小,直接dfs一下每个点的所有可能情况即可,然后利用set的去重特性求出方案数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

const int N = 7;

int a[N][N];
int n, m, k;
set<int> s;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int i, int j, int cnt, int num)
{
    if (cnt >= k + 1)
    {
        s.insert(num);
        return;
    }
    
    for (int t = 0; t < 4; t ++ )
    {
        int x = i + dx[t], y = j + dy[t];//偏移量
        
        if (x >= 1 && x <= n && y >= 1 && y <= m)
        {
            dfs(x, y, cnt + 1, num * 10 + a[x][y]);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> a[i][j];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            dfs(i, j, 1, a[i][j]);
    
    cout << s.size() << endl;
    
    return 0;
}
上一篇:选股,涨幅,收益率排行前面的好股票


下一篇:EXCEL导出