読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 037

algorithm algorithm-動的計画法 contest contest-atcoder language language-c++

abc037.contest.atcoder.jp
DPの問題.
{(i,j)}を始点とする場合の数はその点の周囲のマス+1になる.あとは再帰的に計算してメモ化すればできる.

ll T[1010][1010];
ll dp[1010][1010];
int h, w;
 
ll f(int x, int y, ll p)
{
  if(x<0||x>=h||y<0||y>=w) return 0;
  if(p >= T[x][y]) return 0;
  if(dp[x][y]!=0) return dp[x][y];
  dp[x][y] = (f(x,y-1,T[x][y])+f(x,y+1,T[x][y])+f(x-1,y,T[x][y])+f(x+1,y,T[x][y])+1)%MOD;
  return dp[x][y];
}
 
int main()
{
  scanf("%d %d",&h,&w);
  REP(i,h) REP(j,w) scanf("%lld",&T[i][j]);
  ll ans = 0;
  REP(i,h) REP(j,w) ans = (ans+f(i,j,0))%MOD;
  printf("%lld\n",ans);
  return 0;
}