The 2025 ICPC 德国 German Collegiate Programming Contest——F. Fair and Square · znzryb

## 题目大意

**题目背景**
Felix 的生日派对上，一张 $H \times W$ 的矩形披萨被客人吃掉了一些部分，剩下的部分由若干 $1 \times 1$ 的正方形单元格组成。

**题目描述**
给出一个 $H \times W$ 的网格，其中字符 `#` 表示剩下的披萨块，`.` 表示已经被吃掉（空缺）的部分。
你需要将所有剩下的披萨块（`#`）划分成若干个边长为 $k$ 的正方形区域。
要求：

1. 每个划分出的正方形必须完全由 `#` 组成。

1. 所有 `#` 必须被恰好覆盖一次（不能重叠，不能遗漏）。

1. 只能沿网格线切割。

1. 划分出的所有正方形边长必须相等。

求满足上述条件的最大边长 $k$。

**输入格式**
第一行包含两个整数 $H$ 和 $W$ ($1 \le H, W \le 2500$)，表示网格的高度和宽度。
接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，由 `#` 和 `.` 组成。
保证输入中至少包含一个 `#`。

**输出格式**
输出一个整数，表示最大的可行边长 $k$。

**样例 1**

```
Input
4 7
####...
####.##
.######
.####..

Output
2
```

**样例 1 解释**
对于第一个样例，最大边长为 2。
剩下的披萨块可以被划分为 5 个 $2 \times 2$ 的正方形，其左上角坐标 $(r, c)$ 分别为：$(0,0), (0,2), (1,5), (2,1), (2,3)$。
所有 `#` 均被这 5 个正方形不重不漏地覆盖。

![image](https://media.znzryb.com/20260212-edb929ac/image_e0d26269.png)

这道题说白了其实意思很简单，就是**井号的地方代表就是披萨**，然后你要**把披萨切成正方形的，大小相同的块**，问这些切出来的正方形块的**最大边长**是多少？

**样例 2**

```
Input
3 5
#####
#####
###..

Output
1
```

**样例 3**

```
Input
3 5
.##..
#####
##.##

Output
1
```

**样例 4**

```
Input
5 13
....###......
....###..###.
.######..###.
.###.....###.
.###.........

Output
3
```

## 思路讲解

首先呢我们还是要想到啊，就是我我们首先还是要想到一个算法，能够判定在此边长下能否切割出这样子的东西啊。

这个算法的时间复杂度就是 $O (H \times W)$ 就行，可以了。

这算法其实很简单，也不需要前缀和啊什么之类的。其实只需要一个贪心即可。就说白了，最上面的那个点，**最上面最左边的那个点**，或者你倒过来做最最左边最上面的那个点。你不放一个正方形在上面，就不以这个正方形，**不放一个正方形在这里的话，没有正方形可以覆盖这个点**，***所以这里必须放一个正方形***。就这个披萨点。必须放一个正方形。那么你放了这，放下去这个正正方形以后，你就判断一下这个正方形会不会和其他你放的正方形重叠，啊什么之类的就行了。说白了就是一个贪心。 

```cpp
		auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
```

现在问题就来到什么呢？就是我不可能枚举2500次是吧？枚举2500次就超了。那我怎么样枚举的次数少一点？我其实就加一个非常简单的一个判定即可。**它 cnt 的因数数量肯定是根号下 cnt，也就是数量级是2500**。又因为 i 乘 i 才是 才能组成 cnt 的一个因数，所以实际上 i 只有50的量级。

```cpp
    for (ll i=min(N,M);i>=2;--i) {
        if (cnt%(i*i)!=0) {
            continue;
        }
        if (check(i)) {
            cout<<i<<"\n";
            return;
        }
    }
    cout<<1<<"\n";
```

## AC代码

AC
[https://codeforces.com/gym/106129/submission/362620886](https://codeforces.com/gym/106129/submission/362620886)



::: 源代码

```cpp
/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    ll cnt=0;
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
            if (maze[x][y]=='#') {
                ++cnt;
            }
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    for (ll i=min(N,M);i>=2;--i) {
        if (cnt%(i*i)!=0) {
            continue;
        }
        if (check(i)) {
            cout<<i<<"\n";
            return;
        }
    }
    cout<<1<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    sieve(2600);
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106129/submission/362620886

*/
```


:::


## 心路历程（WA，TLE，MLE……）

WA

[https://qoj.ac/submission/2030500](https://qoj.ac/submission/2030500)



::: 出问题的代码

```cpp
/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    ll ans=1;
    for (ll len=2;len*len<=max(N,M);++len) {
        if (check(len)) {
            ans*=len;
        }
    }
    ans=min(ans,min(N,M));
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/
```


:::


上面这个代码的问题是出在哪里呢？首先第一啊，就是这个因数啊，你直接乘起来，它去找这个最大，其实是不大对的。那么在 m 比较小的情况下，不如直接倒序遍历 m ，然后检验这个 m 的所有的素因数。是否全部都在我们可以凑出来的素因数集合之中。

不过后面我们发现更加大的问题，就是它这个道题目，它其实并不符合说有这个因数，然后我们乘，然后它就能够合在一起，即只要素因数合法，那么所凑出来的合数也合法，这其实是不对的，它们乘起来的合数是不一定合法的。其实很简单吧，就是边长为2和边长为3是没有反例的（**即满足边长为2和满足边长为3，在不限制这个长度的情况下，应该是有满足边长为6的解决方案**）。这个状况，让我们造成了一些错觉，以为说这个其实是可以乘的。但实际上不是这样子的。**满足边长为2，那一定满足边长为4吗？**一定满足边长为8吗？你看它这个2，它可以乘，它，但是它乘上去它就不一定对了。