algorithm - 我们如何找到带有两个不同 "ID"的图的最大连续区域？

Question

我最近了解了Flood-Fill算法，该算法可以绘制图形并以O(N)时间为每个节点分配一个组件号。
例如，可以使用Flood-Fill算法有效解决的一个常见问题是在N*N板中找到最大的区域，其中该区域中的每个节点都与另一个具有相同ID的节点直接相邻，直接向上，向下，左边还是右边

在此板中，最大的区域都是3号，分别由全1和全9组成。
但是，我最近开始怀疑我们是否可以扩展这个问题。具体来说，如果我们可以在图形中找到最大的区域，以使该区域中的每个节点都与另一个具有和可能ID的节点相邻。在上面的面板中，最大的此类区域由1和9组成，大小为7。
这是我尝试解决此问题的过程:
思想1:O(N ^ 4)算法
我们可以使用基本的Flood-fill算法在O(N^4)时间内解决此问题。我们通过测试水平或垂直相邻正方形的所有O(N^2)对来完成此操作。对于每对正方形，如果它们具有不同的ID，则我们从两个正方形之一进行泛洪填充。
然后，通过修改泛洪填充算法，使其以两个可能的ID之一移动到正方形，我们可以在O(N^2) time-> O(N^2) pairs * O(N^2) flood fill per pair = O(N^4) algorithm中测试每一对。
然后，我有了一个见解:可能是O(N ^ 2)算法
首先，我们对电路板进行常规的洪水填充，然后将电路板分成一个“组件图”(原始图中的每个组件都简化为一个节点)。

现在，我们通过组件图的边缘而不是节点进行泛洪填充。我们在每个边缘上用一对整数进行标记，这些整数表示它所连接的两个组件内部的两个ID，然后通过边缘进行泛洪填充，就好像它们本身是节点一样。
我相信，如果实现正确，这将导致O(N^2)算法，因为N*N板上边缘数量的上限是4*N*N。
现在，我的问题是，我的思考过程在逻辑上是否合理？如果没有，有人可以建议另一种算法来解决这个问题吗？

Answer 1

这是我为解决您的问题而编写的算法。它扩展了您的想法，可以通过边缘填充(顺便说一下，是个好主意)，并且能够为250*250网格输出少于300ms的正确答案，并分配少于30 MB的内存。
这是我设法在网上找到与您的问题完全匹配的问题，也是我测试算法有效性的地方:
USACO Problem
请注意，USACO问题要求我们在找到最大的双ID分量之前先找到最大的单ID分量。在我的算法中，第一步实际上是必要的，以便将整个电路板简化为一个组件图。
这是我评论过的C++代码:

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

// board to hold square ids and comp[][] to mark component numbers
vector <vector<int>> board, comp;
vector <int> comp_size = {-1}; // size of those components
vector <int> comp_id = {-1}; // id contained within those components
vector <unordered_set <int>> adj = {{}}; // component graph adjacency list
vector <bool> visited; // component graph visited array

void dfs(int x, int y, int N, int id, int curr_comp){
    if(x < 0 || x >= N || y < 0 || y >= N){return;}
    else if(board[x][y] != id){
        if(comp[x][y] == 0){return;}

        // construct component graph adjacency list during the first flood-fill
        adj[comp[x][y]].insert(curr_comp);
        adj[curr_comp].insert(comp[x][y]);
        // this is why we use an unordered_set: it automatically eliminates
        // collisions

        return;
    }
    else if(comp[x][y]){return;}

    ++comp_size[curr_comp];
    comp[x][y] = curr_comp;

    dfs(x-1, y, N, id, curr_comp);
    dfs(x+1, y, N, id, curr_comp);
    dfs(x, y-1, N, id, curr_comp);
    dfs(x, y+1, N, id, curr_comp);
}

void dfs2(int curr, int id1, int id2, int &size){
    visited[curr] = true;

    // recurse from all valid and adjacent components to curr
    vector <int> to_erase;
    for(int item : adj[curr]){
        if(visited[item]){continue;}
        if(comp_id[item] == id1 || comp_id[item] == id2){
            to_erase.push_back(item);
            size += comp_size[item];
            dfs2(item, id1, id2, size);
        }
    }

    // we erase all edges connecting the current component AT THE SAME TIME to
    // prevent std::unordered_set iterators from being invalidated, which would
    // happen if we erased items as we iterated through adj[curr]
    for(int item : to_erase){
        adj[curr].erase(item);
        adj[item].erase(curr);
    }

    return;
}

int main()
{
    ifstream fin("multimoo.in");
    ofstream fout("multimoo.out");

    int N;
    fin >> N;

    board = vector <vector<int>> (N, vector <int> (N));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            fin >> board[i][j];
        }
    }
    // Input Done

    comp = vector <vector<int>> (N, vector <int> (N, 0)); // note that comp[i][j] = 0 means not visited yet

    // regular flood-fill through all the nodes
    for(int i = 0, curr_comp = 1; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(comp[i][j]){continue;}

            // add information about the current component
            comp_size.push_back(0);
            comp_id.push_back(board[i][j]);
            adj.push_back({});

            dfs(i, j, N, board[i][j], curr_comp++);
        }
    }

    fout << *max_element(comp_size.begin(), comp_size.end()) << endl;

    int ANS = 0;
    for(unsigned int i = 1; i < comp_size.size(); ++i){
        // no range-for loop here as we erase elements while iterating, which
        // may invalidate unordered_set iterators; instead, we use a while-loop
        while(!adj[i].empty()){
            int size = comp_size[i], curr = *(adj[i].begin());
            visited = vector <bool> (comp_size.size(), false); // reset visited
            dfs2(i, comp_id[i], comp_id[curr], size);
            ANS = max(ANS, size);
        }
    }

    fout << ANS << endl;

    return 0;
}

至于时间的复杂性，我个人不是很确定。如果有人可以帮助分析此算法以确定其复杂性，我将不胜感激!