分田地

暴力搜索加剪枝

#include <iostream>
#include <algorithm>
using namespace std;
//grid是输入的田地
string grid[75];
//sum[i][j]是从[1][1]到[i][j]之间所有田的价值和，为了直观下标从1算起
int sum[80][80];
//计算(row1,col1)和(row2,col2)为对角线的区域田地价值之和
int getsum(int row1,int row2,int col1,int col2) {
    return sum[row1][col1] - sum[row1][col2] - sum[row2][col1] + sum[row2][col2];
}
//三横三竖切成16块,ans[i][j]对应着第i行第j列这一小块的价值和
int ans[5][5];
int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n;i ++) {
        cin >> grid[i];
    }
    //计算具体每一个sum
    for(int i = 1;i <= n;i ++) {
        for(int j = 1;j <= m;j ++) {
            sum[i][j] = - sum[i-1][j-1] + grid[i-1][j-1] - '0' + sum[i-1][j] + sum[i][j-1];
        }
    }
        //ansf是最终返回的结果，min_ans记录当前搜索最小值
        int ansf = 0;
        int min_ans = 0;
        //横着切的第一刀
        for(int row1 = 1;row1 < n - 2;row1 ++) {
        //如果切的第一刀分出来的上半部分小于4*ansf或者下半部分小于等于12*ansf，说明无论如何分，总会有一个区域小于ansf，因为均值小于ansf的原因。
            if(sum[row1][m] <= 4*ansf || sum[n][m] - sum[row1][m] <= 12 *ansf) continue;
            //横着切第二刀
            for(int row2 = row1 + 1;row2 < n -1;row2 ++ ){
            //同样类似的剪枝方法
                if(sum[row2][m] - sum[row1][m] <= 4 * ansf || sum[n][m] - sum[row2][m] <= 8* ansf) continue;
                for(int row3 = row2+1;row3 < n; row3 ++) {
                    if(sum[row3][m] - sum[row2][m] <= 4 * ansf || sum[n][m] - sum[row3][m] <= 4 * ansf) continue;
                    //竖着切第一刀，此时可以求出所有16个区域中的左数第一列中的4个子区域
                    for(int col1 = 1;col1 < m - 2;col1 ++) {
                        ans[1][1]= sum[row1][col1];
                        ans[1][2] = sum[row2][col1] - sum[row1][col1];
                        ans[1][3] = sum[row3][col1] - sum[row2][col1];
                        ans[1][4] = sum[n][col1] - sum[row3][col1];
                        min_ans = ans[1][1];
                        for(int d = 2;d <=4;d ++) {
                            min_ans = min(min_ans,ans[1][d]);
                        }
                        //竖着第一刀后，逐行判断每一行在竖切一刀后右边的均值是否小于等于ansf
                        int b1 = sum[row1][m] - sum[row1][col1];
                        if(b1 <= 3 * ansf) continue;
                        min_ans = min(min_ans,b1);
                        int b2 =getsum(row2,row1,m,col1);
                        if(b2 <= 3 * ansf) continue;
                        min_ans = min(min_ans,b2);
                        int b3 = getsum(row3,row2,m,col1);
                        if(b3 <= 3 * ansf) continue;
                        min_ans = min(min_ans,b3);
                        int b4 = getsum(n,row3,m,col1);
                        if(b4 <= 3 * ansf) continue;
                        min_ans = min(min_ans,b4);
                        if(min_ans <= ansf) continue;
                        //同样的思路判断竖切第二刀
                        for(int col2 = col1+1;col2 < m - 1;col2 ++) {
                            ans[2][1] = sum[row1][col2] - sum[row1][col1];
                            ans[2][2] = sum[row2][col2] - sum[row2][col1] - sum[row1][col2] + sum[row1][col1];
                            ans[2][3] = sum[row3][col2] - sum[row3][col1] - sum[row2][col2] + sum[row2][col1];
                            ans[2][4] = sum[n][col2] - sum[n][col1] - sum[row3][col2] + sum[row3][col1];
                            min_ans = ans[2][1];
                            for(int d = 2;d <=4;d ++) {
                                min_ans = min(min_ans,ans[2][d]);
                            }
                            int b1 = sum[row1][m] - sum[row1][col2];
                            if(b1 <= 2 * ansf) continue;
                            int b2 = sum[row2][m] + sum[row1][col2] - sum[row1][m] - sum[row2][col2];
                            if(b2 <= 2 * ansf) continue;
                            int b3 = sum[row3][m] + sum[row2][col2] - sum[row2][m] - sum[row3][col2];
                            if(b3 <= 2 * ansf) continue;
                            int b4 = sum[n][m] + sum[row3][col2] - sum[row3][m] - sum[n][col2];
                            if(b4 <= 2 * ansf) continue;
                            min_ans = min(min_ans,b1);
                            min_ans = min(min_ans,b2);
                            min_ans = min(min_ans,b3);
                            min_ans = min(min_ans,b4);
                            if(min_ans <= ansf){
                                continue;
                            }
                            //同样思路竖切第三刀
                            for(int col3 = col2+1;col3 < m;col3 ++) {
                                ans[3][1] = sum[row1][col3] - sum[row1][col2];
                                ans[3][2] = sum[row2][col3] - sum[row2][col2] - sum[row1][col3]+sum[row1][col2];
                                ans[3][3] = sum[row3][col3] - sum[row3][col2] - sum[row2][col3]+sum[row2][col2];
                                ans[3][4] = sum[n][col3] - sum[n][col2] - sum[row3][col3]+sum[row3][col2];
                                min_ans = ans[3][1];
                                for(int d = 2;d <=4;d ++) {
                                    min_ans = min(min_ans,ans[3][d]);
                                }

                                ans[4][1] = sum[row1][m] - sum[row1][col3];
                                ans[4][2] = sum[row2][m] - sum[row2][col3] - sum[row1][m]+sum[row1][col3];
                                ans[4][3]= sum[row3][m] - sum[row3][col3] - sum[row2][m]+sum[row2][col3];
                                ans[4][4] = sum[n][m] - sum[n][col3] - sum[row3][m]+sum[row3][col3];
                                for(int d = 1;d <=4;d ++) {
                                    min_ans = min(min_ans,ans[4][d]);
                                }
                                    int minf = ans[1][1];
                                    for(int c1=  1;c1 <=4 ;c1 ++ ) {
                                        for(int c2 = 1;c2 <= 4;c2 ++) {
                                            minf = min(minf,ans[c1][c2]);
                                        }
                                    }
                                    if(minf < ansf) continue;
                                    else {
                                        ansf = minf;
                                    }
                            }
                        }
                    }
                }
            }
        }
        cout << ansf << endl;

}