题目链接
先从小到大去排个序
想着记录每行每列当前最大值，然后就取两者最大值+1就行了
但是相同的数字因为行列不一，条件也不一样苛刻，所以要是能修改的时候把所有相同的数字也修改就好了
所以并查集，只关心根节点的值就好了
这里想漏了一点，并不是所有相同的数字都要相同，因为他们其实互不管辖，除了同行同列的相同数字。
#include #include #include #include #include #include using namespace std; #define MAXN 1000005 int f[MAXN],Size[MAXN],val[MAXN]; int find(int x) { return f[x]==x ? x : f[x] = find(f[x]); } inline void merge(int x,int y) { int fx = find(x), fy = find(y); if(fx==fy) return; if(Size[fx]> N >> M; for(int i=1;i<=N*M;++i) { f[i] = i; Size[i] = 1; } for(int i=1;i<=N;++i) { for(int j=1;j<=M;++j) { cin >> a[(i-1)*M+j].num; a[(i-1)*M+j].x = i; a[(i-1)*M+j].y = j; a[(i-1)*M+j].pos = (i-1)*M+j; } } sort(a+1,a+1+N*M,cmp2); for(int i=2;i<=N*M;++i) { if(a[i].x==a[i-1].x&&a[i].num==a[i-1].num) merge(a[i].pos,a[i-1].pos); } sort(a+1,a+1+N*M,cmp3); for(int i=2;i<=N*M;++i) { if(a[i].y==a[i-1].y&&a[i].num==a[i-1].num) merge(a[i].pos,a[i-1].pos); } sort(a+1,a+1+N*M,cmp1); for(int i=1;i<=N*M;++i) { int fx = find(a[i].pos); if(X[a[i].x]==0&&Y[a[i].y]==0) { if(val[fx]==0) val[fx] = 1; } else { if(fx!=X[a[i].x]) val[fx] = max(val[fx],val[find(X[a[i].x])]+1); if(fx!=Y[a[i].y]) val[fx] = max(val[fx],val[find(Y[a[i].y])]+1); } X[a[i].x] = Y[a[i].y] = fx; } for(int i=1;i<=N;++i) { for(int j=1;j<=M;++j) cout << val[find((i-1)*M+j)] << " "; cout << "\n"; } return 0; }