题目描述

有一个 $N\times N$（$1\le N\le 1000$）的矩阵，其中第 $r$ 行第 $c$ 列的方格中的整数为 $r+c$。

有 $3$ 种操作。

1. 交换两行；
2. 交换两列；
3. 选择两个同时存在于表格中的值 $a$ 和 $b$，然后同时将每一个 $a$ 更改为 $b$，每一个 $b$ 更改为 $a$。

Elsie 总是按类型顺序执行操作；也就是说，她首先执行任意数量（可能为零）的类型 $1$ 操作，然后是类型 $2$ 操作，最后是类型 $3$ 操作。

请求出在执行完所有类型 $1$ 和 $2$ 操作后，在执行任意类型 $3$ 操作之前，矩阵的一种可能状态。可能存在多种可能的答案，在这种情况下你应当输出字典序最小的答案。

思路

首先有一个性质：执行完 $1$、$2$ 操作后，每一行每一列的数字会变成原来的行、列的排列，就是一开始与 $2$ 在同一行的是 $3$ 到 $2+n-1$，执行完 $1$、$2$ 操作后，与 $2$ 在同一行的还是 $3$ 到 $2+n-1$。

显然，$1$ 操作交换行，行内部的数字不会变，$2$ 操作交换列，行内部相当于交换 $2$ 个数的顺序，不会改变值，只会改变顺序。$1$ 操作交换行列内部相当于交换 $2$ 个数的数字，不会改变值，只会改变顺序，$2$ 操作交换列，列内部的数字不会变。所以执行完 $1$、$2$ 操作后，每一行每一列的数字只会变顺序，一开始与 $2$ 在同一行同一列的数字执行完 $1$、$2$ 操作后还是与 $2$ 在同一行同一列。

然后，只有一开始的第 $1$ 行有 $2$，一开始的最后 $1$ 行有 $n\times 2$，$2$ 和 $n\times 2$ 都只出现了一次，很好确定位置，与 $2$ 在同一行的是 $2$ 到 $n+1$，与 $n\times 2$ 在同一行的是 $n+1$ 到 $n\times 2$，通过出现次数刚好可以确定所有的数，因为出现次数是 $1$ 的有 $2$ 个数，我们不知道哪个是 $1$ 哪个是 $n\times 2$，所以答案有 $2$ 种，我们分两种情况算完后比较字典序即可。

代码

#include<iostream>
#include<cstring>
using namespace std;
int n,a[1005][1005],cnt[2005],fa[2005],s1,s2,ans1[1005][1005],ans2[1005][1005];
int check()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(ans1[i][j]<ans2[i][j])
				return true;
			if(ans1[i][j]>ans2[i][j])
				return false;
		}
	}
	return 924;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			cnt[a[i][j]]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		bool flag=false;
		for(int j=1;j<=n;j++)
		{
			if(cnt[a[i][j]]==1)
			{
				if(!s1)
					s1=i;
				else
				{
					s2=i;
					flag=true;
					break;
				}
			}
		}
		if(flag)
			break;
	}
	for(int i=1;i<=n;i++)
	{
		fa[a[s1][i]]=cnt[a[s1][i]]+1;
		fa[a[s2][i]]=n*2-cnt[a[s2][i]]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			ans1[i][j]=fa[a[i][j]];
	}
	for(int i=1;i<=n;i++)
	{
		fa[a[s1][i]]=n*2-cnt[a[s1][i]]+1;
		fa[a[s2][i]]=cnt[a[s2][i]]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			ans2[i][j]=fa[a[i][j]];
	}
	if(check())
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				printf("%d ",ans1[i][j]);
			printf("\n");
		}
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				printf("%d ",ans2[i][j]);
			printf("\n");
		}
	}
}