c++dfs进阶题代码求解

Question

题目描述

给定一个迷宫，由 H 行 W 列字符组成，其中. 可以走，# 不可以走。
有一个魔法师从起点 (Ch,Cw) 出发，目标是走到终点 (Dh,Dw)。
每一次他可以向上、下、左、右移动一格。
他还可以使用魔法，瞬间移动到以他现在的位置为中心的 5 * 5 的正方形中的任意位置。
输出这个魔法师最少使用几次魔法，才能到达终点位置(Dh,Dw)。

输入

第一行两个数H和W
第二行两个数Ch和Cw代表起点坐标
第三行两个数Dh和Dw代表终点坐标
接下来的表示H行和W列的代表迷宫数据

输出

输出最少使用魔法的次数，如果不能到达终点，输出-1

样例输入 Copy

4 4
1 1
4 4
..#.
..#.
.#..
.#..

样例输出 Copy

1

提示

数据范围：
1<＝H，W<=10^3
起点终点坐标不重合。

c++完整代码

Answer 1

下午好🌅🌅🌅
本答案参考ChatGPT-3.5

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int dfs(vector<vector<int>>& maze, int ch, int cw, int dh, int dw, int dest) {
        if (ch == dest || abs(dh - dw) <= 2 || abs(ch - cw) <= 2 || abs(dh - ch) <= 2) return 0;
        
        if (maze[ch][cw] != '#') return 0; // 白色不能走
        
        for (int i = 1; i <= maze.size(); ++i) {
            vector<vector<int>> temp(maze[i].size(), vector<int>(4));
            
            for (int j = 0; j <= maze[i].size(); ++j) {
                temp[j][0] = maze[i][j];
                temp[j][1] = maze[i][j+1];
                temp[j][2] = maze[i][j+2];
                temp[j][3] = maze[i][j+3];
            }
            
            int cost = dfs(temp, ch + 1, cw, dh, dw, dest);
            if (cost > 0)
                return cost;
        }
        
        return -1; // 最少需要4次魔法
    }

private:
    vector<vector<int>> maze;
};

int main() {
    Solution solution;
    vector<vector<int>> maze = {{1, 1, 0, 0, 0},
                                {1, 0, 1, 0, 0},
                                {0, 1, 0, 1, 1},
                                {0, 0, 1, 1, 0},
                                {0, 0, 0, 1, 1}};
    
    int ch = 1, cw = 1;
    int dh = 0, dw = 0;
    int dest = 4;
    
    cout << "Solution: " << solution.dfs(maze, ch, cw, dh, dw, dest) << endl;
    
    return 0;
}

在这个代码中，我们首先定义了一个名为Solution的类，并实现了dfs函数来解决这个问题。该函数接受迷宫的二维数组和当前位置作为参数，以及目标位置和魔法等级。dfs函数的主要逻辑是递归地搜索所有可能的路径，每次循环更新当前状态，并递归地计算新的路径。

我们还定义了起始和结束点坐标，以及魔法等级的目标值。最后，我们在主函数中创建了一个迷宫对象，并调用了dfs函数来获取最少使用的魔法次数。