S.G.G's blog

By S.G.G, history, 8 years ago, In English

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;//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]);
}

  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?