[??记录]AT4113 [ARC095C] Symmetric Grid
command_block
2021-05-04 19:32:23
**题意** : 给定一个包含小写字母的矩阵，每次可以整体交换两行或两列，求是否可以将其变成一个中心对称的矩阵。
$n,m\leq 12$ ，时限$\texttt{2s}$。
------------
先枚举列的置换，然后考虑如何判定是存在交换行的方案使得合法。
对于给定的 $n$ 个字符串，需要两两配对（若总数为奇数，剩下的必须是回文串），满足 $S_1={\rm reverse}(S_2)$。
字符串哈希一手，可以用 `long long` 装下，于是容易 $O\big(n(m+n)\big)$ 判定是否匹配。
若枚举所有的置换，复杂度为 $O(n!nm)$ ，无法通过。
实际上，我们只关心列翻转后的两两对应，故只需要枚举所有的匹配。而匹配的数目是 $11\times 9\times 7\times 5\times 3\times 1=10395$ 的，于是可以通过。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
int n,m,p[15];
char s[15][15];
ll s1[15],s2[15];
bool vis[15],ans;
void dfs(int cnt,bool fl)
{
if (cnt==m){
for (int i=1;i<=n;i++){
s2[i]=0;
for (int j=1;j<=m;j++)
s2[i]=s2[i]*26+s[i][p[j]]-'a';
}
for (int i=1;i<=n;i++)vis[i]=0;
int tmp=0;
for (int i=1;i<=n;i++)if (!vis[i]){
bool fl=0;
for (int j=i+1;j<=n;j++)
if (!vis[j]&&s1[i]==s2[j])
{vis[j]=fl=1;break;}
if (!fl){
if (s1[i]!=s2[i])return;
tmp++;
}
}ans|=(tmp<=1);
return ;
}
int i=1;while(p[i])i++;
if (fl){p[i]=i;dfs(cnt+1,0);p[i]=0;}
for (int j=i+1;j<=m;j++)if (!p[j]){
p[i]=j;p[j]=i;
dfs(cnt+2,fl);
p[i]=p[j]=0;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for (int j=1;j<=m;j++)
s1[i]=s1[i]*26+s[i][j]-'a';
}
dfs(0,m&1);
puts(ans ? "YES" : "NO");
return 0;
}
```