Submission #1804620

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int dp[42][42][42][42];
// x1, x2, y1, y2

int psums[41][41];

int q(LL a1, LL a2, LL b1, LL b2){
    return psums[a2][b2] - psums[a1][b2] - psums[a2][b1] + psums[a1][b1];
}
int main(){
    int h, w;
    cin >> h >> w;
    string g[h];
    for(int i = 0; i < h; i++){
        cin >> g[i];
    }
    int px, py;

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(g[i][j] == 'P'){
                g[i][j] = '+';
                px = i;
                py = j;
            }
        }
    }
    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            psums[i][j] = 0;
            if(i == 0 || j == 0) continue;
            psums[i][j] = psums[i][j-1] + psums[i-1][j] - psums[i-1][j-1];
            if(g[i-1][j-1] == '#') psums[i][j]++;
        }
    }

    for(int a1 = h; a1 >= 0; a1--){
        for(int a2 = a1; a2 <= h; a2++){
            for(int b1 = w; b1 >= 0; b1--){
                for(int b2 = b1; b2 <= w; b2++){
                    dp[a1][a2][b1][b2] = 1000000;
                    int k = 1000000;
                    for(int am = a1; am <= a2; am++){
                        for(int bm = b1; bm <= b2; bm++){
                            int al = a1;
                            int ar = a2;
                            int bl = b1;
                            int br = b2;
                            if(px >= am) al = am;
                            if(px < am) ar = am;
                            if(py >= bm) bl = bm;
                            if(py < bm) br = bm;
                            k = min(k, q(al, ar, bl, br));
                            int ans2 = dp[al][ar][bl][br];
                            ans2 += q(al,ar,b1+bm-bl,bm+b2-br);
                            ans2 += q(a1+am-al,am+a2-ar,bl,br);
                            k = min(k, ans2);
                        }
                    }
                    dp[a1][a2][b1][b2] = min(dp[a1][a2][b1][b2], k);
                }
            }
        }
    }
    cout << dp[0][h][0][w] << endl;
}

Submission Info

Judge Result