Problem Link

Solution

There is no harm in assumptioning that all the values in the table

are unique.Then it gets easier to think out the solution of the

problem.We can sort all the values from small to large and insert

them into the final matrix one by one and change the value into the

maximum value in the same row or column at present.It will be the

final value after it added one.Then how to solve this problem when

the values are not unique?How can we deal with the elements with the

same value?We can use Union-Find Sets to merge the elements that have

the same value and limit each other.Obviously the elements in the

same union will have same final values and there is no limit from a

union to another.Then the solution is similar to before.

Code

#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
using namespace std;
struct hh
{
	int n,x,y,v;
} a[1000001];
int n,m,i,j,t,lt,p,fa[1000001],ans[1000001],la[1000001],lb[1000001],fi[1000001],h[1000001],l[1000001],b[1000001];
void add(int x,int y)
{
	la[++lt]=y; lb[lt]=fi[x]; fi[x]=lt;
}

int find(int x)
{
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

bool cmp1(hh a,hh b)
{
	return a.v<b.v || (a.v==b.v && a.x<b.x);
}

bool cmp2(hh a,hh b)
{
	return a.y<b.y;
}

void bfs(int x)
{
	int k,mx=max(h[(x-1)/m+1],l[(x-1)%m+1]);
	for (k=fi[x];k;k=lb[k])
		mx=max(mx,max(h[(la[k]-1)/m+1],l[(la[k]-1)%m+1]));
	for (k=fi[x];k;k=lb[k]) 
		ans[la[k]]=h[(la[k]-1)/m+1]=l[(la[k]-1)%m+1]=mx+1;
	ans[x]=h[(x-1)/m+1]=l[(x-1)%m+1]=mx+1;
}

int main()
{
		scanf("%d%d\n",&n,&m);
		for (i=1;i<=n;i++,scanf("\n"))
			for (j=1;j<=m;j++)
			{
				t++;
				scanf("%d",&a[t].v);
				a[t].n=t;
				a[t].x=i;
				a[t].y=j;
			}
		sort(a+1,a+t+1,cmp1);
		for (i=1;i<=t;i++) fa[i]=i;
		for (i=1;i<=t;i=p+1)
		{
			lt=0;
			p=i;
			while (p<t && a[p+1].v==a[p].v) p++;
			for (j=i+1;j<=p;j++)
				if (a[j].x==a[j-1].x) fa[find(a[j].n)]=find(a[j-1].n);
			sort(a+i,a+p+1,cmp2);
			for (j=i+1;j<=p;j++)
				if (a[j].y==a[j-1].y) fa[find(a[j].n)]=find(a[j-1].n);
			for (j=i;j<=p;j++) find(a[j].n);
			for (j=i;j<=p;j++) add(fa[a[j].n],a[j].n);
			for (j=i;j<=p;j++)
				if (fa[a[j].n]==a[j].n) bfs(a[j].n);
		}
		for (i=1;i<=n;i++,printf("\n"))
			for (j=1;j<=m;j++) printf("%d ",ans[(i-1)*m+j]);
}