c++ - 这个 C++ 片段中的缓冲区溢出在哪里？

Question

我使用以下解决方案遇到缓冲区溢出https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

class Solution {
public:
    struct pt {
        int x;
        int y;
        int k;
        int s;
        pt(int x, int y, int k, int s): s(s), x(x), y(y), k(k) {}
    };
    
    int shortestPath(vector<vector<int>>& grid, int k) {
        int height = grid.size(), width = grid[0].size();
        std::vector<std::pair<int, int>> dirs {{1,0}, {0, 1}, {-1, 0}, {0, -1}};
        std::vector<std::vector<int>> maxKs(height, std::vector<int>(width, -1));
        std::queue<pt> q;
        q.push(pt(0, 0, k, 0));
        
        while ( !q.empty() ) {
            auto f = q.front(); 
            q.pop();
            if (f.x == width-1 && f.y == height-1) return f.s;
            
            if (maxKs[f.x][f.y] >= f.k || f.k < 0) continue;
            maxKs[f.x][f.y] = f.k;
            
            for (auto dir : dirs) {
                int x = f.x + dir.first;
                int y = f.y + dir.second;
                if (x < 0 || y < 0 || x == width || y == height) continue;
                int curK = f.k - (grid[x][y] == 1);
                if (curK < 0) continue;
                q.push(pt(x,y,curK,f.s + 1));
            }
        }
        
        return -1;
    }
};

想知道是否有人对这里发生的事情有想法？

标签： c++overflow

Answer 1

您将尺寸声明为

        int height = grid.size(), width = grid[0].size();

但是您使用width的是 的元素数grid和height的数grid[x]。

maxKs[f.x][f.y]应该是maxKs[f.y][f.x]，grid[x][y]应该是grid[y][x]。