java - 在矩阵java中找到相等数字的最大区域

Question

我有一个任务。我需要找到具有相同数量的最大区域(例如，按行或列的邻居)。我制作的程序运行良好，但问题是如果我有以下矩阵:

{ 1, 3, 2, 2, 2, 4 } 
{ 3, 1, 3, 2, 4, 4 }
{ 4, 3, 1, 2, 3, 3 }  
{ 4, 3, 1, 3, 3, 1 }  
{ 4, 3, 3, 3, 1, 1 }

程序将打印 10。好吧，也许你们中的一些人会说这是因为我将 1 添加到最终结果，是的，这是真的，但是如果我不添加 1，并且如果位置 [1][1 ] 是 3 而不是 1，我会得到 12 女巫是错误的，所以这就是我加 1 的原因。所以我的问题是你对优化算法有什么建议吗..如果是的话，我将非常感谢听到他们:)..

这是我的代码:

protected  int counter = 0;
    protected  int max = 1;
    protected enum eState {
        Vi,
        InPr,
        Unvi
    };

    public void recNodeMatrix(int i, int j, eState st[][],int [][]matr,int n,int k) {

        st[i][j] = eState.InPr;

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < k; c++) {
                if ((matr[i][j] == matr[r][c]) 
                        && ((((i+j) - (r + c)) == 1) || (((i+j) - (r + c)) == -1))
                        && ((st[r][c] == eState.Unvi))) { 
                    counter++;
                    recNodeMatrix(r, c, st,matr,n,k); 
                }
            }
        }
        st[i][j] = eState.Vi;
    }


    public  void Zad17() {

        int n=5,k=6;
        eState st[][] = new eState[n][k];

        int[][] matr = new int[][] {
                { 1, 3, 2, 2, 2, 4 },
                { 3, 1, 3, 2, 4, 4 },
                { 4, 3, 1, 2, 3, 3 },
                { 4, 3, 1, 3, 3, 1 },
                { 4, 3, 3, 3, 1, 1 } };



        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                st[i][j] = eState.Unvi;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                if(st[i][j] == eState.Unvi) {
                    recNodeMatrix(i, j, st,matr,n,k);
                    if(max<counter)
                        max=counter;
                    counter =0;
                }
            }
        }


        System.out.print(max+1);
    }

Answer 1

解决这个问题的最好方法可能是使用联合查找数据结构:https://en.wikipedia.org/wiki/Disjoint-set_data_structure

最初，每个单元格都是它自己的集合，然后您合并每对相邻单元格中具有相同数字的集合。

完成后，答案就是最大集合的大小。由于无论如何您都必须跟踪集合大小，因此请使用按大小并集而不是按等级并集。

运用一点小聪明，您可以仅使用一组 N*K 整数来实现联合查找——每个单元一个。每个整数要么是父集的索引，要么是根的 -size。

这在大约线性时间内解决了问题，并且在实践中可能比使用类似内存量的洪水填充解决方案更快。