📝 题目大意

给定两个 $H$ 行 $W$ 列的网格 $S$ 和 $T$（由 # 和 . 组成），判断是否可以通过对 $S$ 的列进行重新排列，使其与 $T$ 完全相同。

💡 解题思路

1. 题目分析：重新排列列意味着可以选择任意 $1 \sim W$ 的排列 $P$，将 $S$ 的第 $j$ 列移动到第 $P_j$ 列。由于 $P$ 可以是任意排列，本质上就是问：$S$ 的 $W$ 列的多重集与 $T$ 的 $W$ 列的多重集是否相同。数据范围 $1 \le H \times W \le 4 \times 10^5$，保证了 $O(HW)$ 的算法可行。

2. 算法推导：

   • 将每一列看作一个长度为 $H$ 的字符串（由上到下拼接该列的所有字符）。
   • 代码中用 cnt[0][j] 存储 $S$ 的第 $j$ 列，cnt[1][j] 存储 $T$ 的第 $j$ 列。
   • 读入时逐行处理，将每个字符追加到对应列的字符串末尾，即实现了行列转置。
   • 将 $S$ 和 $T$ 各自的 $W$ 个列字符串分别排序。排序后，如果两个多重集相同，排序结果必然一一对应相等。
   • 逐列比较排序后的结果，若全部相等则输出 Yes，否则输出 No。

3. 边界与细节：

   • $H=1$ 或 $W=1$ 的情况：算法仍然正确。当 $W=1$ 时，只有一个列，排序后直接比较即可。
   • $S = T$ 的情况：显然排序后全等，输出 Yes。
   • 列字符串长度较大（$H \le 4 \times 10^5$），但总字符数不超过 $4 \times 10^5$，排序比较的总开销可控。
   • 注意数组下标从 $1$ 开始，排序时使用 cnt[n] + 1 到 cnt[n] + w + 1。

⏱️ 复杂度分析

• 时间复杂度：$O(HW + W \log W \cdot H)$。其中 $HW$ 是构建列字符串的开销，$W \log W \cdot H$ 是排序 $W$ 个长度为 $H$ 的字符串的比较开销。由于 $HW \le 4 \times 10^5$，总操作量在可接受范围内。
• 空间复杂度：$O(HW)$，用于存储两套列字符串。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
signed main() {
	int h, w;
	// cnt[0] 存储 S 的各列，cnt[1] 存储 T 的各列
	string cnt[2][400010] = {};
	cin >> h >> w;
	// n = 0 处理 S，n = 1 处理 T
	for (int n = 0; n <= 1; n++)
		for (int i = 1; i <= h; i++) {
			string s;
			cin >> s;
			// 将第 i 行的每个字符追加到对应列的字符串中，实现行列转置
			for (int j = 1; j <= w; j++)
				cnt[n][j] += s[j - 1];
		}
	// 对 S 和 T 的列字符串分别排序
	for (int n = 0; n <= 1; n++)
		sort(cnt[n] + 1, cnt[n] + w + 1);
	// 逐列比较，若有不相等则说明两个多重集不同
	for (int i = 1; i <= w; i++)
		if (cnt[0][i] != cnt[1][i]) {
			cout << "No";
			return 0;
		}
	cout << "Yes";
    return 0;
}