洛谷P9417
刻意的想让大家练练搜索。
首先能想到的是，显然枚举了长度之后，答案只有两种可能，就是从左上角横着/竖着放。
确定了之后，就有诸多限制：
比如一定得是的倍数。
比如对于每一种字符，它在目标串出现的次数乘以必须得恰好等于总次数，诸如此类。
显然符合条件的个数最多只有几十种。
然后就是一个典型的精确覆盖问题了。
这个可以用dancing links来进行加速。
但实际上，你可以大胆一点猜一下，如果有解，那么解其实很密集，如果无解，那么怎么搜不搜不到解，于是写一个相对优雅的爆搜，直接记一个，一旦超过你搜索的次数还无解，就直接当没有解，就可以过了。
题外话：正解实际上给了一个结论：如果有解的话，对于当前考虑的格子，一定是能横着放就横着放，不能横着放才竖着放，但是正解是波兰语，看不懂具体证明。
#include <bits/stdc++.h>
#define ll long long
#define maxn 1105
#define mod 998244353
using namespace std;
int n, m;
string s[maxn];
int num[30], ok[maxn];
string amb = " ", pre;
bool vis[maxn][maxn];
int tag, siz;
basic_string<int> ans;
int lim = 0;
int can(int x, int y, int dx, int dy) {
if (dx && x + siz - 1 >= n)
return 0;
if (dy && y + siz - 1 >= m)
return 0;
for (int i = 0; i < siz; i++, x += dx, y += dy) {
if (s[x][y] != amb[i] || vis[x][y])
return 0;
}
return 1;
}
void dfs(int x, int y) {
if (tag)
return;
while (x != n && vis[x][y]) {
y++;
if (y == m)
y = 0, x++;
}
if (x == n) {
tag = 1;
return;
}
lim += siz;
if (lim >= n * m * 5)
return;
if (can(x, y, 0, 1)) {
for (int i = 0; i < siz; i++) vis[x][y + i] = 1;
dfs(x, y + siz - 1);
for (int i = 0; i < siz; i++) vis[x][y + i] = 0;
}
if (can(x, y, 1, 0)) {
for (int i = 0; i < siz; i++) vis[x + i][y] = 1;
dfs(x, y);
for (int i = 0; i < siz; i++) vis[x + i][y] = 0;
}
return;
}
int main() {
freopen("druk.in", "r", stdin);
freopen("druk.out", "w", stdout);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> s[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) num[s[i][j] - 'a']++;
// cout<<num[0]<<" "<<num[1]<<endl;
for (siz = 1; siz <= max(n, m); siz++, amb = amb + ' ')
if (n * m % siz == 0) {
int flag = 0;
for (int j = 0; j <= 25; j++)
if (num[j] % (n * m / siz) != 0)
flag = 1;
if (flag)
continue;
tag = 0;
memset(vis, 0, sizeof(vis));
if (siz <= m) {
for (int i = 0; i < siz; i++) amb[i] = s[0][i];
int tot[27];
memset(tot, 0, sizeof(tot));
for (int i = 0; i < siz; i++) tot[amb[i] - 'a']++;
int zong = n * m / siz, ff = 0;
for (int i = 0; i < 26; i++)
if (zong * tot[i] != num[i])
ff = 1;
pre = amb;
lim = 0;
if (!ff)
dfs(0, 0);
}
memset(vis, 0, sizeof(vis));
if (siz <= n) {
for (int i = 0; i < siz; i++) amb[i] = s[i][0];
int tot[27];
memset(tot, 0, sizeof(tot));
for (int i = 0; i < siz; i++) tot[amb[i] - 'a']++;
int zong = n * m / siz, ff = 0;
for (int i = 0; i < 26; i++)
if (zong * tot[i] != num[i])
ff = 1;
lim = 0;
if (amb != pre && !ff)
dfs(0, 0);
}
if (tag)
ans += siz;
}
cout << (int)(ans.size()) << endl;
for (int i : ans) cout << i << " ";
cout << endl;
}