0

I am trying to solve Q1091 on LeetCode. In order to solve this question, I create a class called "Queue":

class Queue {
public:
    int x;
    int y;
    int length;
    Queue(int xx, int yy, int l): x(xx), y(yy), length(l) {};
};

The entire class "Solution" is like below:


class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid);
    void addNewQueue(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& path, int length, vector<Queue>& queues);
};

int Solution::shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return -1; //means there is no maze to be solve
    if (grid[0][0] == 1) return -1;
    vector<vector<int>> path(grid.size());
    for (auto &r: path) r.resize(grid.size(), INT_MAX);
    path[0][0] = 0;
    vector<Queue> queues;
    queues.push_back(Queue(0, 0, 0));
    while (!queues.empty()) {
        auto q = queues.begin();
        addNewQueue(grid, q->x+1, q->y, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y, path, q->length, queues);
        addNewQueue(grid, q->x+1, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x+1, q->y-1, path, q->length, queues);
        addNewQueue(grid, q->x, q->y-1, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y-1, path, q->length, queues);
        queues.erase(queues.begin());
    }
    if (path[path.size()-1][path.size()-1] == INT_MAX) return -1;
    else return path[path.size()-1][path.size()-1];
}
void Solution::addNewQueue(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& path, int length, vector<Queue>& queues) {
    if (x < grid.size() && y < grid.size() && x >= 0 && y >= 0 && length+1 < path[x][y] && grid[x][y] == 0) {
        queues.push_back(Queue(x, y, length+1));
        path[x][y] = length + 1;
    }

    return;
}

Yet, whenever Solution::addNewQueue runs, the program crash with error below:

=================================================================
==31==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000110 at pc 0x000000347b34 bp 0x7ffdc8ec3510 sp 0x7ffdc8ec3508
READ of size 4 at 0x602000000110 thread T0
    #2 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000110 is located 0 bytes inside of 12-byte region [0x602000000110,0x60200000011c)
freed by thread T0 here:
    #5 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
previously allocated by thread T0 here:
    #5 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 00 fa
  0x0c047fff8010: fa fa fd fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8020: fa fa[fd]fd fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

I have tried to search for the reason but cannot find one. Please help me with the issue. Thank you.

I have read a question be answered: How can I create objects while adding them into a vector?

Yet, the solution does not work.

EDITION:: Here's a sample main.cpp:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    Solution s;
    vector<vector<int>> grid(2);
    for (auto& c:grid) c.resize(2);
    grid[0][0] = 0;
    grid[0][1] = 1;
    grid[1][0] = 1;
    grid[0][1] = 0;
    cout << grid[0][0] << " " << grid[0][1] << endl;
    cout << grid[1][0] << " " << grid[1][1] << endl;
    cout << s.shortestPathBinaryMatrix(grid);
    
}

The error might not pop out in some compiler. Instead, the point would point to a random memory.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
李承軒
  • 1
  • 1
  • Please provide a very short `main` function that uses the `Solution` class in such a way that it reproduces the issue. – Ted Lyngmo Jan 27 '23 at 15:38
  • `queues.push_back()` call invalidates iterators into `queues`, including `q`. After the first `addNewQueue` call, `q` may become invalid, but you continue to use it. Whereupon your program exhibits undefined behavior. – Igor Tandetnik Jan 28 '23 at 16:06
  • Are you aware of [`std::queue`](https://en.cppreference.com/w/cpp/container/queue) class? You are trying to simulate it with `vector`, poorly. – Igor Tandetnik Jan 28 '23 at 16:08
  • Indeed, it seems as though you can just use the std::queue instead of trying to make one. If your compiler does not note capitalization, your computer might be displaying an error over a renaming issue. – Hudson Feb 12 '23 at 17:15

0 Answers0