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;//Serial number
int x;//row
int y;//column
int v;//value
} a[1000001];
int n,m,i,j,t,lt,p,fa[1000001],ans[1000001],la[1000001],lb[1000001],fi[1000001],h[1000001],l[1000001];
//fa[] array used in Union-Find Sets
//ans[] the final answer
//la[] The target point (Adjacency list)
//lb[] Pointer (Adjacency list)
//fi[] Pointer to the last line (Adjacency list)
//h[i] the maximum in row i
//l[i] the maximum in column i
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]);
}