C++基于BFS求解矩阵最长路径时控制台输入大矩阵挂起问题

功能需求 #

求解N×M规模矩阵中的最长合法路径，规则如下：

• 仅可向右（记为J）或向下（记为L）移动
• 每次移动后下一个格子与当前格子的数值差绝对值≤k
• 最终输出三个结果：路径长度、起始格子坐标、起点到终点的移动序列

问题现象 #

采用广度优先搜索（BFS）实现功能，小矩阵输入下运行正常，输入200×200规模矩阵时：

• 通过控制台输入数据：程序无响应挂起
• 通过文件读取输入：程序正常运行

相关代码 #

#include <iostream>
#include <stdlib.h>
#include <queue>
#include <vector>
#include <fstream>
#include <chrono>

using namespace std;
using namespace std::chrono;

struct pr {
    int i;
    int j;
};

void read(int arr[][301], int &n, int &m, int &k) {
    // 冗余代码：定义了文件流但未使用
    ifstream be("be.txt");
    int i, j;
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
}

bool checkRight(int arr[][301], int i, int j, int k, int m) {
    if (j + 1 <= m && abs(arr[i][j + 1] - arr[i][j]) <= k)
        return 1;
    return 0;
}

bool checkDownwards(int arr[][301], int i, int j, int k, int n) {
    if (i + 1 <= n && abs(arr[i + 1][j] - arr[i][j]) <= k)
        return 1;
    return 0;
}


void bfs(int dist[][301], int arr[][301], bool visited[][301], int i, int j, int n, int m, int k, int &max, pr &po, vector<int> &resol) {
    int maxDist = 0;
    int l, p;
    pr prev[301][301];
    for (l = 1; l <= n; l++) {
        for (p = 1; p <= m; p++) {
            prev[l][p].i = 0;
            prev[l][p].j = 0;
        }
    }
    pr pos;
    pos.i = 0;
    pos.j = 0;
    vector<int> res;
    queue<pr> q;
    pr next;
    next.i = i;
    next.j = j;
    for (l = 1; l <= n; l++) {
        for (p = 1; p <= m; p++) {
            dist[l][p] = 0;
        }
    }
    dist[i][j] = 0;
    visited[i][j] = 1;
    q.push(next);
    while (!q.empty()) {
        pr front = q.front();
        visited[front.i][front.j] = 1;
        q.pop();
        if (checkRight(arr, front.i, front.j, k, m) == 1) {
            next.i = front.i;
            next.j = front.j + 1;
            q.push(next);
            dist[front.i][front.j + 1] = dist[front.i][front.j] + 1;
            maxDist = dist[front.i][front.j + 1];
            pos.i = next.i;
            pos.j = next.j;
            prev[next.i][next.j].i = front.i;
            prev[next.i][next.j].j = front.j;
        }
        if (checkDownwards(arr, front.i, front.j, k, n) == 1) {
            next.i = front.i + 1;
            next.j = front.j;
            q.push(next);
            dist[front.i + 1][front.j] = dist[front.i][front.j] + 1;
            maxDist = dist[front.i + 1][front.j];
            pos.i = next.i;
            pos.j = next.j;
            prev[next.i][next.j].i = front.i;
            prev[next.i][next.j].j = front.j;
        }
    }

    if (maxDist > max) {
        max = maxDist;
        po.i = i;
        po.j = j;
        resol.clear();
        next.i = pos.i;
        next.j = pos.j;
        while (next.i != i or next.j != j) {
            if (next.i == prev[next.i][next.j].i) {
                resol.push_back(1);
                next.j = prev[next.i][next.j].j;
            }
            if (next.j == prev[next.i][next.j].j) {
                resol.push_back(0);
                next.i = prev[next.i][next.j].i;
            }
        }
    }

}

void search(int arr[][301], int n, int m, int k) {
    int max = 0;
    int dist[301][301];
    bool visited[301][301] = {0};
    int i, j;
    vector<int> resol;
    pr po;
    po.i = 0;
    po.j = 0;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (visited[i][j] == 0)
                bfs(dist, arr, visited, i, j, n, m, k, max, po, resol);
        }
    }
    cout << max << endl;
    cout << po.i << " " << po.j << endl;
    for (i = resol.size() - 1; i >= 0; i--) {
        if (resol[i] == 0)
            cout << "L";
        else
            cout << "J";
    }
}

int main() {
    auto start = high_resolution_clock::now();
    int n, m, k;
    int arr[301][301];
    read(arr, n, m, k);
    search(arr, n, m, k);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<seconds>(stop - start);
    cout<<endl<<duration.count();
}

测试用例 #

小矩阵测试用例 #

输入

5 4 1
7 7 9 7
4 5 3 4
6 6 5 2
4 7 8 2
1 2 3 4

输出

4
2 1
JLLJ
0

200×200大矩阵测试用例 #

输出

• 控制台输入：程序挂起无响应
• 文件输入：

20
183 53
LLJJJJJLJLLJLLLLLJLL
3

问题原因与解决方案 #

核心原因 #

C++的cin默认开启了与C标准IO流的同步，且默认每次输入后都会刷新输出缓冲区，导致大批量数据输入时性能极差。控制台输入的读写速度本身远低于文件读取，叠加cin的性能损耗，就会出现程序看起来无响应挂起的现象。

修复方案 #

在read函数开头添加两行代码，关闭cin的同步和自动刷新：

ios::sync_with_stdio(false);
cin.tie(nullptr);

同时可以删除read函数中未使用的ifstream be("be.txt");冗余代码。
修复后控制台输入大矩阵的速度会提升至和文件读取相当的水平，不会再出现挂起问题。

内容的提问来源于stack exchange，提问作者Dani Suba