Codeforces Round #745(Div.2) C.Portal 二维前缀和

**题目大意：**给定一个矩阵，问最少通过多少部能够打出一个长大于等于 5 5 5，宽大于等于 4 4 4的传送门来。

**思路：**数据范围 400 400 400，暴力枚举四条边必然会超时，因此考虑优化方式-二维前缀和：

• 翻转次数 = 中间区域 1 1 1数量 + 四边中 0 0 0的数量 - 四个角如果有 0 0 0就减相应个数；
• 对于每个点 ( x , y ) (x, y) (x,y)分别从 x + 4 , y + 3 x+4,y+3 x+4,y+3入手开始扩展，每次计算总前缀和与内部前缀和相减，便是反转次数；
• 可以剪枝。如果当前已扫描到答案且扩展后的答案更大，那么就略过。

#include 
using namespace std;

const int N = 500;
int g[N][N], f[N][N];

inline int get(int a, int b, int c, int d){ return f[a][b] + f[c - 1][d - 1] - f[a][d - 1] - f[c - 1][b]; }

inline void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1; i  s;
            g[i][j] = s - '0';
        }
    for(int i = 1; i