【蓝桥】动态规划-多维dp-地图(带有转向次数限制)

  

问题描述 

解题思路

🌟1、例子：经典的迷宫问题

🌟2、状态定义

 🌟3、转移方程

完整代码

问题描述 

​

问题实质：
··------需要在一个网格中从 (1,1)移动到 (n,m)，统计满足转向次数不超过 k 且不经过石头的有效路径数量。 

解题思路

对于普通的地图问题，我们直接利用深度优先搜索即可解决 。  

🌟1、例子：经典的迷宫问题

我们有一个迷宫地图，空格表示可以通行的区域，# 表示墙壁，起点为 (1, 1)，终点为 (n, m)。我们的目标是通过 DFS 搜索所有从起点到终点的路径。

#include <bits/stdc++.h>
using namespace std;

const int N = 101;
int n, m;  // 地图的行列数
char s[N][N];  // 地图
bool visited[N][N];  // 访问标记
vector<pair<int, int>> path;  // 当前路径

// 方向数组：0 -> 上, 1 -> 右, 2 -> 下, 3 -> 左
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 深度优先搜索
void dfs(int x, int y) {
    // 如果越界或遇到墙壁或已经访问过，直接返回
    if (x < 1 || x > n || y < 1 || y > m || s[x][y] == '#' || visited[x][y]) {
        return;
    }

    // 标记当前位置为已访问
    visited[x][y] = true;
    path.push_back({x, y});  // 将当前节点加入路径

    // 如果到达终点，输出路径
    if (x == n && y == m) {
        for (auto p : path) {
            cout << "(" << p.first << ", " << p.second << ") ";
        }
        cout << endl;
    } else {
        // 尝试四个方向进行深度优先搜索
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            dfs(nx, ny);  // 递归搜索
        }
    }

    // 回溯：取消访问标记，移除路径
    visited[x][y] = false;
    path.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] + 1;  // 输入地图
    }

    // 从(1,1)开始DFS
    dfs(1, 1);

    return 0;
}

但是本题有一个限制，就是变换的方向只能有k次。那么我们要如何去思考这个限制呢，不妨在我们搜索的时候不仅记录位置，还记录一个变换方向的次数【记忆化搜索】，当没有变换次数的时候就不允许在变换了。好，我们解决了变换方向的限制，那么要如何记录方案数呢?考虑利用动态规划。

🌟2、状态定义

 🌟3、转移方程

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int dp[N][N][2][6];  // dp[x][y][d][step]：在位置(x, y)，方向为d，已转向次数为step时的路径数
char s[N][N];
int dx[2]={0,1}, dy[2]={1,0};  // 方向数组：0->右，1->下
int n, m, k;

int dfs(int x, int y, int d, int step) {
    // 越界或遇到石头或转向超限，直接返回0
    if (x > n || y > m) return 0;
    if (s[x][y] == '#') return 0;
    if (step > k) return 0;

    // 成功到达终点，返回1条有效路径
    if (x == n && y == m) return 1;

    // 如果当前状态已计算过，直接返回结果
    if (dp[x][y][d][step] != -1) return dp[x][y][d][step];

    int res = 0;
    // 状态转移：尝试向右或向下移动
    for (int i = 0; i < 2; i++) {
        res += dfs(x + dx[i], y + dy[i], i, step + (i != d)); // 转向则step+1
    }

    // 保存当前状态的结果以供后续查询
    return dp[x][y][d][step] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) 
        cin >> s[i] + 1; // 读入地图

    // 初始化dp数组为-1，表示未计算过
    memset(dp, -1, sizeof(dp));

    int ans = 0;
    // 从(1,1)出发，尝试第一步向右或向下
    if (s[1][2] != '#') ans += dfs(1, 2, 0, 0); // 向右
    if (s[2][1] != '#') ans += dfs(2, 1, 1, 0); // 向下

    cout << ans << "\n"; // 输出有效路径数量
    return 0;
}