2023华为od机试 C++ 【路径步数。】

男娘i 2024-03-08 08:40 44阅读 0赞

### 题目 ###

小明喜欢户外运动，这个周末他打算去附近的山区探险，他面前有一张特殊的地图来帮助他找到这片区域的最高点。

这张地图是一个由数字构成的网格。网格中的每一个单元格包含一个数字，代表那个点的高度。其中，数字 0 代表平地，而数字 1 到 9 则代表不同的高度。小明可以向上下左右任何一个方向移动到相邻的单元格中。

然而，小明不是超人，他不能一下子爬得太高或者降得太低。他每次能够爬升或下降的高度差是有限制的，他能够克服的最大高度差是 k。

现在小明站在地图的左上角（0,0 位置），他想知道：

在他的爬升和下降限制下，他能够到达的最高点是多少？  
到达那个点需要多少步？

输入描述  
第一行包含三个整数，分别是 m、n 和 k。其中 m 和 n 代表地图的行数和列数，k 代表小明可以克服的最大高度差。  
接下来的 m 行每行包含 n 个整数，描述了整个地图的高度信息。  
输出描述  
输出两个整数，分别表示：  
小明可以到达的最高点的高度。  
到达那个最高点所需要的最少步数。  
如果小明无法到达任何一个点，那么输出 0 0。

示例  
输入

5 4 1  
0 1 2 0  
1 0 0 0  
1 0 1 2  
1 3 1 0  
0 0 0 9

输出

2 2

解释

根据地图，小明可以到达的最高点是 (0,2) 位置，高度为 2。他可以通过下面的路径到达那里：

(0,0) → (0,1) → (0,2)  
这条路径包含 2 步。

### 代码 ###

#include <iostream>
    #include <vector>
    #include <map>
    #include <limits.h>
    #include <string>
    
    using namespace std;
    
    vector<pair<int, int> > dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
    
    void getInput(int& m, int& n, int& k, vector<vector<int> >& grid) {
        
        m = 5; n = 4; k = 1;
        grid = {
        
            {
        0, 1, 2, 0},
            {
        1, 0, 0, 0},
            {
        1, 0, 1, 2},
            {
        1, 3, 1, 0},
            {
        0, 0, 0, 9}
        };
    }
    
    void dfs(const vector<vector<int> >& grid, int m, int n, int k, int x, int y, int step, map<int, int>& hSteps) {
        
        int prevH = grid[x][y];
    
        for(auto dir : dirs) {
        
            int newX = x + dir.first;
            int newY = y + dir.second;
    
            if(newX >= 0 && newX < m && newY >= 0 && newY < n) {
        
                int currH = grid[newX][newY];
    
                if(abs(currH - prevH) <= k) {
        
                    ++step;
    
                    if(hSteps.find(currH) == hSteps.end() || hSteps[currH] > step) {
        
                        hSteps[currH] = step;
                    }
    
                    dfs(grid, m, n, k, newX, newY, step, hSteps);
                    --step;
                }
            }
        }
    }
    
    string getResult(int m, int n, int k, const vector<vector<int> >& grid) {
        
        map<int, int> hSteps;
        hSteps[grid[0][0]] = 0;
    
        dfs(grid, m, n, k, 0, 0, 0, hSteps);
    
        if(hSteps.size() == 1 && hSteps.begin()->first == 0) {
        
            return "0 0";
        }
    
        int maxH = 0;
        int minS = INT_MAX;
    
        for(auto hs : hSteps) {
        
            int h = hs.first;
            int s = hs.second;
            
            if(h > maxH || (h == maxH && s < minS)) {
        
                maxH = h;
                minS = s;
            }
        }
    
        return to_string(maxH) + " " + to_string(minS);
    }
    
    int main() {
        
        int m, n, k;
        vector<vector<int> > grid;
        
        getInput(m, n, k, grid);
        
        cout << getResult(m, n, k, grid) << endl;
        
        return 0;
    }