Codeforces 24 D. Broken robot

問題

N行M列のグリッドがある。
このグリッドのi行j列にロボットがいて、
ロボットは1ターンに1度次の動きのうち、可能なものを等確率で一つ実行する。

  • その場から動かない
  • 一列下の列に動く(最下段についたら止まる)
  • 左に動く(グリッドからはみでる場合は不可能)
  • 右に動く(上に同じ)

ロボットが停止するまでにかかるターン数の期待値を小数点4桁まで求めよ。

制約条件

N,M≦1000

方針

ある一行の期待値が全て求まっていれば、その一行上の行の期待値は、
1000次の連立方程式を解くことで決定できる。


しかし、1000次の連立方程式を1000回解くのは計算時間が間に合わない。
そのため、期待値が収束するまで100回程度ループを回してやる。


これで必要な精度の答えが計算できる。

ソースコード

const int iter=100;
int n,m,y,x;
double e[1000][1000];

void run(){
  cin>>n>>m>>y>>x;
  y--; x--;
  if(y==n-1){
    cout<<0<<endl;
    return;
  }
  for(int i=n-2;i>=y;i--){
    rep(_,iter)rep(j,m){
      int cnt=2;
      double s=e[i+1][j]+e[i][j];
      if(j>0)s+=e[i][j-1], cnt++;
      if(j<m-1)s+=e[i][j+1], cnt++;
      e[i][j]=1+s/cnt;
    }
  }
  printf("%.9f\n",e[y][x]);
}