bzoj1616 [Usaco2008 Mar]Cow Travelling游荡的奶牛(dp)

dp水题。试了下滚动数组。 O(nmt)

#include <cstdio> #include <cstring> #define N 105 int n,m,t,dp[2][N][N],x1,y1,x2,y2; char map[N][N]; int main(){ // freopen("a.in","r",stdin); scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;++i) scanf("%s",map[i]+1); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); memset(dp,0,sizeof(dp));int p=0; dp[p][x1][y1]=1; for(int tt=1;tt<=t;++tt){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(map[i][j]=='.') dp[p^1][i][j]=dp[p][i-1][j]+dp[p][i+1][j]+dp[p][i][j-1]+dp[p][i][j+1]; p^=1; } printf("%d\n",dp[p][x2][y2]); return 0; }