分析:
DP水题
反过来考虑终点在移动
设终点移动过的最左,右,上,下的点,构成一个矩形,显然在矩形内部移动是没有代价的。
所以只需要考虑如何拓展这个矩形:如果矩形左移一格,那么右侧一部分点就再也到不了了,如果矩形上移一格,那么下侧一部分点就再也到不了了,这些点的数量可以统计出来。
然后求出终点的移动区间为整个区间时,至少删了多少个点。
转移很简单,分当前矩形是否与边界相交即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 105
using namespace std;
typedef long long ll;
int n,m,sum,ex,ey;
char s[MAXN][MAXN];
short int dp[MAXN][MAXN][MAXN][MAXN];
int addx[MAXN][MAXN][MAXN],addy[MAXN][MAXN][MAXN];
ll add1(int new1,int d,int l,int r){
int l1=r-ey+1;int r1=l+m-ey;if(new1>d)return addx[new1][l1][r1];elsereturn addx[new1][l1][l-1]+addx[new1][r+1][r1];
}
ll add2(int new1,int u,int l,int r){
int l1=r-ey+1;int r1=l+m-ey;if(new1<u)return addx[new1][l1][r1];elsereturn addx[new1][l1][l-1]+addx[new1][r+1][r1];
}
ll add3(int new1,int r,int u,int d){
int u1=d-ex+1;int d1=u+n-ex;if(new1>r)return addy[new1][u1][d1];elsereturn addy[new1][u1][u-1]+addy[new1][d+1][d1];
}
ll add4(int new1,int l,int u,int d){
int u1=d-ex+1;int d1=u+n-ex;if(new1<l)return addy[new1][u1][d1];elsereturn addy[new1][u1][u-1]+addy[new1][d+1][d1];
}
int min1(int x,int y){
if(x==-1)return y;if(y==-1)return x;return min(x,y);
}
int dfs(int u,int d,int l,int r){
if(dp[u][d][l][r]!=-1)return dp[u][d][l][r];if(u<ex){
dp[u][d][l][r]=min1(dp[u][d][l][r],dfs(u+1,d,l,r)+add1(u+1+n-ex,d,l,r));}if(d>ex){
dp[u][d][l][r]=min1(dp[u][d][l][r],dfs(u,d-1,l,r)+add2(d-ex,u,l,r));}if(l<ey){
dp[u][d][l][r]=min1(dp[u][d][l][r],dfs(u,d,l+1,r)+add3(l+1+m-ey,r,u,d));}if(r>ey){
dp[u][d][l][r]=min1(dp[u][d][l][r],dfs(u,d,l,r-1)+add4(r-ey,l,u,d));}//PF("[%d %d %d %d %d(%d)]\n",u,d,l,r,dp[u][d][l][r],addy[1][1][n]);return dp[u][d][l][r];
}
int main(){
SF("%d%d",&n,&m);for(int i=1;i<=n;i++)SF("%s",s[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=j;k<=m;k++)addx[i][j][k]=addx[i][j][k-1]+(s[i][k]=='o'); for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)for(int k=j;k<=n;k++)addy[i][j][k]=addy[i][j][k-1]+(s[k][i]=='o');for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
if(s[i][j]=='E'){
ex=i;ey=j;}if(s[i][j]=='o')sum++;}memset(dp,-1,sizeof dp);dp[ex][ex][ey][ey]=0;PF("%d\n",sum-dfs(1,n,1,m));}