连通分量程序产生不正确的输出

Question

我正在开发一个程序，它接受一个 5x5 的字符数组并找到最长的相同字符列表，连接意味着相邻的上、下、左或右（意味着没有对角线）。但是输出偏移 1，给出 6 而不是正确的 7，输入：

a b c c b
a c b c c
c a a b a
b b a a c
a a a b a

谁能帮我找出我的代码中的错误是什么？ （我的代码如下）

详情： 缺失字符位于索引 [3][3]（索引从 0 开始）。当我测试我的 look() 函数时，它工作正常，当我将 3 传递给行，将 2 传递给列时，它向要返回的最终向量添加了 [3][3]，但我认为有些东西确实递归不正确。

我已经调试过了，没有成功，你可以在我的代码中看到调试打印。

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <utility>

using namespace std;
char grid[5][5];
bool seen[5][5];
int cnt = 1;
int maxn = 0;

vector<pair<int, int>> look(int row, int col)
{
    //
    vector<pair<int, int >> node_list;
    if (row != 0)
        if (grid[row - 1][col] == grid[row][col])
            if (!seen[row - 1][col])
                node_list.push_back(make_pair(row - 1, col));
    if (row != 4)
        if (grid[row + 1][col] == grid[row][col])
            if (!seen[row+1][col])
                node_list.push_back(make_pair(row + 1, col));
    if (col != 0)
        if (grid[row][col - 1] == grid[row][col])
            if (!seen[row][col-1])
                node_list.push_back(make_pair(row, col - 1));
    if (col != 4)
        if (grid[row][col + 1] == grid[row][col])
            if (!seen[row][col+1])
                node_list.push_back(make_pair(row, col + 1));
    if (binary_search(node_list.begin(), node_list.end(), make_pair(2, 2)))
        cout << "HAPPENED^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^" << "\n";
    return node_list;
}

void search(int row, int col)
{
    for (pair<int, int> a : look(row, col))
    {
        if (!seen[a.first][a.second])
        {
            seen[a.first][a.second] = true;
            cnt++;
            cout << "COUNTED and now SEARCHING " << a.first << " " << a.second << "\n";
            cout << "search about to be called on " << a.first << " " << a.second << "\n";
            search(a.first, a.second);
        }
    }
    if (cnt > maxn)
        maxn = cnt;
    cout << "CNT: " << cnt << "\n";
    cnt = 1;
    return;
}

int main()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> grid[i][j];
            seen[i][j] = false;
        }
    }

    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            if (!seen[i][j])
            {
                cout << "INITIALLY SEARCHING: " << i << " " << j << "\n";
                seen[i][j] = true;
                cout << "search about to be called on " << i << " " << j << "\n";
                search(i, j);
            }
            else
                cout << "NO INITIAL SEARCH, SEEN: " << i << " " << j << "\n";
        }
    }
    cout << maxn << "\n";
    return 0;
}

Answer 1

问题是您正在递归使用 search，但也在其末尾无条件地重置 cnt。

这个问题可以用一个只有 3 个字符的简单 "board" 来演示：

a a a

假设我们从 search 开始，中间 a。它调用 look 并被告知检查另外两个地方：左侧的 a 和右侧的 a。 search 然后调用自己，比方说用左边的 a。此时 cnt 为 2，左侧和中间 a 的 seen 设置为 true。第二个递归 search 调用再次要求 look 查找附近的 a，但这次它们都已经被看到了。所以第二个 search 结束，将 maxn 设置为 2 并且 将 cnt 重置为 1。现在我们回到第一层递归，继续右边的a。不用说，我们已经丢弃了我们在左边计数的一次a。

这里的问题是你没有明确区分 "recursively search nearby fields" 和 "start a search from this point"。你当前的最后两行 search 属于后者而不是前者。我建议这样做：

void searchRecursive(int row, int col)
{
    for (pair<int, int> a : look(row, col))
    {
        if (!seen[a.first][a.second])
        {
            seen[a.first][a.second] = true;
            cnt++;
            searchRecursive(a.first, a.second);
        }
    }
}

void startSearchFrom(int row, int col)
{
    cnt = 1;
    seen[i][j] = true;
    searchRecursive(row, col);
    if (cnt > maxn)
        maxn = cnt;
    cout << "CNT: " << cnt << "\n";
}

这很好地分离了这些问题。

进一步的改进是摆脱所有全局状态。尽管 seen 从未被重置，但您的算法仍能正常工作并不是很明显（尽管是真的），并且验证 cnt 是否正确使用需要牢记 all使用它的地方。如果每个 searchRecursive 都返回它找到了多少个看不见的位置，那么验证结果是否正确将是微不足道的。

连通分量程序产生不正确的输出

Connected component program produces incorrect output

c++

recursion

graph

c++11

connected-components