思路

• 用并查集记录次序临近且位置临近的元素，并查集的根节点是最小的元素，同时记录对应并查集的大小，遍历一遍数组元素即可找到本问题得到答案。
• 时间复杂度为 $O(K \times S^2)$ ，空间复杂度为 $O(S^2)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
int fa[N*N];
int num[N*N];
int s;
bool check(int x,int y){
    if(x>=1&&x<=s&&y>=1&&y<=s) return true;
    return false;
}
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
int main(void){
    int t,i,j,k;
    scanf("%d",&t);
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

    for(k=1;k<=t;k++){
        scanf("%d",&s);
        int ans1=1,ans2=1;
        for(i=1;i<=s;i++){
            for(j=1;j<=s;j++){
                scanf("%d",&g[i][j]);
            }
        }
        for(i=1;i<=s*s;i++){
            fa[i]=i;
            num[i]=1;
        }
        for(i=1;i<=s;i++){
            for(j=1;j<=s;j++){
                int tmp;
                for(tmp=0;tmp<4;tmp++){
                    int x1=i+dx[tmp],y1=j+dy[tmp];
                    if(!check(x1,y1)) continue;
                    else if(!(g[x1][y1]-g[i][j]==1)) continue;
                    else{
                        int t1=find(g[i][j]),t2=find(g[x1][y1]);
                        if(t1==t2) continue;
                        else if(t1<t2){
                            fa[t2]=t1;
                            num[t1]+=num[t2];
                            if(num[t1]>ans2){
                                ans2=num[t1];
                                ans1=t1;
                            }
                            if(ans2==num[t1]&&t1<ans1) ans1=t1;
                        }else{
                            fa[t1]=t2;
                            num[t2]+=num[t1];
                            if(num[t2]>ans2){
                                ans2=num[t2];
                                ans1=t1;
                            }
                            if(ans2==num[t2]&&t2<ans1) ans1=t2;
                        }
                    }
                }
            }
        }
        printf("Case #%d: %d %d\n",k,ans1,ans2);
    }

    return 0;
}