Submission #2148279

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m,x,y;
char f[55][55];
int rui[55][55];
int calc(int a,int b,int c,int d){
	return rui[b][d]-rui[a-1][d]-rui[b][c-1]+rui[a-1][c-1];
}
int dp[45][45][45][45];
int rec(int a,int b,int c,int d){
	if(dp[a][b][c][d] < 100000) return dp[a][b][c][d];
	int &ret = dp[a][b][c][d];
	ret = min(calc(a,x,c,y),ret);
	ret = min(calc(a,x,y,d),ret);
	ret = min(calc(x,b,c,y),ret);
	ret = min(calc(x,b,y,d),ret);
	for(int X=x;X<=b;X++) for(int Y=y;Y<=d;Y++){
		if(X==b && Y==d) continue;
		ret = min(ret,calc(X+1,b,c,Y)+calc(a,X,Y+1,d)+rec(a,X,c,Y));
	}
	for(int X=x;X<=b;X++) for(int Y=c;Y<=y;Y++){
		if(X==b && Y==c) continue;
		ret = min(ret,calc(X+1,b,Y,d)+calc(a,X,c,Y-1)+rec(a,X,Y,d));
	}
	for(int X=a;X<=x;X++) for(int Y=y;Y<=d;Y++){
		if(X==a && Y==d) continue;
		ret = min(ret,calc(a,X-1,c,Y)+calc(X,b,Y+1,d)+rec(X,b,c,Y));
	}
	for(int X=a;X<=x;X++) for(int Y=c;Y<=y;Y++){
		if(X==a && Y==c) continue;
		ret = min(ret,calc(a,X-1,Y,d)+calc(X,b,c,Y-1)+rec(X,b,Y,d));
	}
	return ret;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string str; cin>>str;
		for(int j=1;j<=m;j++){
			f[i][j] = str[j-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j] == 'P'){
				x = i;
				y = j;
			}
			rui[i][j] = (f[i][j]=='#'?1:0);
			rui[i][j] += rui[i-1][j];
			rui[i][j] += rui[i][j-1];
			rui[i][j] -= rui[i-1][j-1];
		}
	}
	rep(i,45)rep(j,45)rep(k,45)rep(l,45)dp[i][j][k][l] = INF;
	cout << rec(1,n,1,m) << endl;
}

Submission Info

Judge Result