预处理从每个位置向每个方向最多能走几步
dp[k][i][j] 第k个时间段后，钢琴到位置（i，j）能走的最长路径
枚举这一次走几步转移
#include#include #include #include using namespace std;int n,m;char mp[201][201];int cnt[5][201][201];int dp[2][201][201];int dx[5]={ 0,-1,1,0,0};int dy[5]={ 0,0,0,-1,1};void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int find(int x,int y,int d){ if(x<=0 || x>n || y<=0 || y>m) return 0; if(mp[x][y]=='x') return 0; cnt[d][x][y]=find(x+dx[d],y+dy[d],d); return cnt[d][x][y]+1;}int main(){ freopen("adv1900.in","r",stdin); freopen("adv1900.out","w",stdout); int x,y,T; read(n); read(m); read(x); read(y); read(T); for(int i=1;i<=n;++i) scanf("%s",mp[i]+1); memset(cnt,-1,sizeof(cnt)); for(int d=1;d<=4;++d) { for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(mp[i][j]=='.' && cnt[d][i][j]==-1) cnt[d][i][j]=find(i+dx[d],j+dy[d],d); } memset(dp[0],-1,sizeof(dp[0])); int now=0,nxt=1; dp[0][x][y]=0; int s,t,d; int len; while(T--) { memset(dp[nxt],-1,sizeof(dp[nxt])); read(s); read(t); read(d); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(dp[now][i][j]!=-1) { len=min(t-s+1,cnt[d][i][j]); for(int k=0;k<=len;++k) dp[nxt][i+k*dx[d]][j+k*dy[d]]=max(dp[nxt][i+k*dx[d]][j+k*dy[d]],dp[now][i][j]+k); } swap(now,nxt); } int ans=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans=max(ans,dp[now][i][j]); printf("%d",ans);}