11055: 【原1055】二哥切巧克力

题目

题目描述

author: oldherl zyz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1055

Description

二哥有一大块矩形平板巧克力，被划分成RxC个小方格。

今天他要从这上面切下一个aichimi形的巧克力送给它的女友。

所谓aichimi形就是一个边长至少为3的正方形切掉四个边长为1的角的形状。下面是一个边长为4的aichimi形：

##

####

##

二哥(此时)只有一个女友所以只要切下一块就可以了。

由于这巧克力是某超市的便宜货，每个方格的密度都不同，可能为0.0至0.9g/cm^2不等。

二哥要求这块aichimi形巧克力的重心恰好在中心处，这样他才能给女友表演一个手指转巧克力的“绝活”。

请问符合要求的最大的aichimi形边长是多少呢？

Input Format

第一行为数据组数T

每组数据第一行两个数R和C，表示巧克力板的大小

接下来的R行每行C个数字字符(0到9)，表示该方格的密度，单位0.1g/cm2

Output Format

共T行

对于每组数据输出一个整数A表示符合要求的最大aichimi形的边长，如果没有则输出IMPOSSIBLE

Hint

\(3 \leq R \leq 300, 3 \leq C \leq 300\)

第一个样例的答案如下图

.......

..222..

.21152.

.32913.

.24212.

..222..

Sample Input

Sample Output

5
IMPOSSIBLE

FineArtz's solution

/* 二哥切巧克力 */
#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int T;
    cin >> T;
    while (T--){
        int c, r;
        char ch;
        int a[305][305], sum[305][305];
        int sumx[305][305], sumy[305][305];
        cin >> r >> c;
        for (int i = 0; i <= r; ++i){
            sum[i][0] = 0;
            sumx[i][0] = 0;
            sumy[i][0] = 0;
        }
        for (int j = 0; j <= c; ++j){
            sum[0][j] = 0;
            sumx[0][j] = 0;
            sumy[0][j] = 0;
        }
        for (int i = 1; i <= r; ++i){
            for (int j = 1; j <= c; ++j){
                cin >> ch;
                a[i][j] = ch - '0';
                sum[i][j] = a[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= r; ++i){
            for (int j = 1; j <= c; ++j){
                sumx[i][j] = sumx[i - 1][j] + i * (sum[i][j] - sum[i - 1][j]);
                sumy[i][j] = sumy[i][j - 1] + j * (sum[i][j] - sum[i][j - 1]);
            }
        }
        bool flag = false;
        for (int k = min(r, c); k >= 3; --k){
            for (int i = 1; i <= r - k + 1; ++i){
                for (int j = 1; j <= c - k + 1; ++j){
                    int x = i + k - 1, y = j + k - 1;
                    int s = sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1]
                            - a[i][j] - a[i][y] - a[x][j] - a[x][y];
                    double wx = sumx[x][y] - sumx[i - 1][y] - sumx[x][j - 1] + sumx[i - 1][j - 1]
                            - i * a[i][j] - i * a[i][y] - x * a[x][j] - x * a[x][y];
                    double wy = sumy[x][y] - sumy[i - 1][y] - sumy[x][j - 1] + sumy[i - 1][j - 1]
                            - j * a[i][j] - y * a[i][y] - j * a[x][j] - y * a[x][y];
                    if (s == 0){
                        flag = true;
                        cout << k << '\n';
                        break;
                    }
                    wx = wx / s;
                    wy = wy / s;
                    if (abs(2 * wx - i - x) < 1e-8 && abs(2 * wy - j - y) < 1e-8){
                        flag = true;
                        cout << k << '\n';
                        break;
                    }
                }
                if (flag) break;
            }
            if (flag) break;
        }
        if (!flag) cout << "IMPOSSIBLE\n";
    }
    return 0;
}