BFS实现矩阵路径查找时遇Double free or corruption错误求助

Hey there! I see you're working on a pathfinding problem using BFS and hitting a double free or corruption error. Let's break down what's going wrong and fix your code step by step.

Problem Recap #

You're tasked with finding a path from the source cell (value 1) to the destination cell (value 2) in an N×N matrix, where you can only move through cells with value 3 (or the destination itself). You're using BFS but encountering memory corruption issues.

Root Causes of the Error #

Let's go through the main issues in your code that lead to the double free/corruption error and logic bugs:

1. Array Index Out-of-Bounds in store
   In your main loop, you're using store[t-1] to save the result. But since t is decremented each iteration (starting from the number of test cases), when t reaches 0, t-1 becomes -1—this is an invalid index, which corrupts memory and causes the double free error.

2. Flawed BFS Logic

   • You check if the current cell is the destination after popping it from the queue but before marking it as visited. This can lead to unnecessary processing.
   • You modify the curr pair when checking neighbors and then revert it, which is error-prone and can lead to incorrect state.
   • The source cell's visited flag is marked in a separate condition instead of when it's enqueued, which can cause it to be reprocessed.

3. Redundant Header Includes
   You're including multiple overlapping headers (stdio.h, iostream, bits/stdc++.h). While not directly causing the error, it's unnecessary—bits/stdc++.h includes most standard library headers already.

Fixed Code #

Here's the corrected version of your code with explanations of key changes:

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

// Check if coordinates are within matrix bounds
bool inside(int first, int second, int r) {
    return first >= 0 && first < r && second >=0 && second < r;
}

int isPath(pair<int, int> source, vector<vector<int>> &adj, vector<vector<bool>> &visit, int r) {
    queue<pair<int, int>> q;
    
    // Mark source as visited and enqueue it immediately
    visit[source.first][source.second] = true;
    q.push(source);
    
    // Directions: up, down, left, right
    vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    while(!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        
        // Check if current cell is the destination
        if(adj[curr.first][curr.second] == 2) {
            return 1;
        }
        
        // Explore all four directions
        for(auto &dir : dirs) {
            int newX = curr.first + dir.first;
            int newY = curr.second + dir.second;
            
            // Check if new position is valid, not visited, and is either 3 or destination (2)
            if(inside(newX, newY, r) && !visit[newX][newY] && (adj[newX][newY] == 3 || adj[newX][newY] == 2)) {
                visit[newX][newY] = true;
                q.push({newX, newY});
            }
        }
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    vector<int> store(t);
    int idx = 0; // Counter to track result index correctly
    
    while(t--) {
        int r;
        cin >> r;
        vector<vector<int>> adj(r, vector<int>(r));
        vector<vector<bool>> visit(r, vector<bool>(r, false)); // Initialize all to false
        pair<int, int> source;
        
        // Read matrix and find source position
        for(int i=0; i<r; i++) {
            for(int j=0; j<r; j++) {
                cin >> adj[i][j];
                if(adj[i][j] == 1) {
                    source = {i, j};
                }
            }
        }
        
        // Save result using correct index
        store[idx++] = isPath(source, adj, visit, r);
    }
    
    // Print all results
    for(int res : store) {
        cout << res << endl;
    }
    
    return 0;
}

Key Fixes Explained #

• Correct store Indexing: We use a separate idx counter that increments each iteration, so we never access invalid negative indices.
• Simplified BFS Direction Handling: Using a direction vector makes the code cleaner and less error-prone than manually checking each direction.
• Proper Visited Marking: We mark the source as visited when enqueuing it, and mark neighbors as visited before enqueuing them to prevent duplicate entries in the queue.
• Early Destination Check: We check if the current cell is the destination right after popping it from the queue, which is the correct time to do so.
• Simplified Initialization: The visit vector is initialized with false directly when created, removing the need for a separate loop.

Testing the Code #

This code should now correctly handle the pathfinding without memory errors. For example, if you input a valid path from 1 to 2 through 3s, it will return 1; if no path exists, it returns 0.

内容的提问来源于stack exchange，提问作者Ankesh Kumar Singh