一、
实际上无后效性是动态规划算法的前提之一，然后有些题，
我们设计出状态表示和状态转移方程之后才发现，其似乎不满足无后效性这一特点。

以 以下 期望dp为例，在很多的题目中，动态规划的状态转移分阶段带环，
我们需要把dp和高斯消元相结合，在整体层面采用动态规划框架，在局部
使用高斯消元解出互相影响的状态。

事实上，多数的期望dp都会采用倒推的方式执行。
Broken robot CodeForces - 24D：
You received as a gift a very clever robot walking on a rectangular board. Unfortunately, you understood that it is broken and behaves rather strangely (randomly). The board consists of N rows and M columns of cells. The robot is initially at some cell on the i-th row and the j-th column. Then at every step the robot could go to some another cell. The aim is to go to the bottommost (N-th) row. The robot can stay at it’s current cell, move to the left, move to the right, or move to the cell below the current. If the robot is in the leftmost column it cannot move to the left, and if it is in the rightmost column it cannot move to the right. At every step all possible moves are equally probable. Return the expected number of step to reach the bottommost row.

Input
On the first line you will be given two space separated integers N and M (1 ≤ N, M ≤ 1000). On the second line you will be given another two space separated integers i and j (1 ≤ i ≤ N, 1 ≤ j ≤ M) — the number of the initial row and the number of the initial column. Note that, (1, 1) is the upper left corner of the board and (N, M) is the bottom right corner.

Output
Output the expected number of steps on a line of itself with at least 4 digits after the decimal point.

Examples
Input
10 10
10 4
Output
0.0000000000
Input
10 14
5 14
Output
18.0038068653

给定一N*M的棋盘，一机器人处于（x，y）位置，这个机器人每次行动可以等概率的向左，向右，向下移动一格，或者停在原地。
当然机器人不能走出棋盘，求机器人从起点，走到最后一行任意一个位置上，所需要移动次数期望值。
列出每一行M个方程之后，发现高斯消元系数矩阵除主对角线和对角线两侧的斜线之外，其余部分为0。
在这样的矩阵中执行高斯消元，在每一行中实际上只有2–3个位置需要相减，O（M）即可求出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=1010;
const int mod=1e9+7;
double dp[maxn][maxn];
double f[maxn][maxn];
double xx[maxn];
int n,m,x,y;

void Guass(void)
{
    for(int i=1;i<m;i++)
    {
        double temp=f[i+1][i]/f[i][i];
        f[i+1][i]-=temp*f[i][i];
        f[i+1][i+1]-=temp*f[i][i+1];
        f[i+1][m+1]-=temp*f[i][m+1];
    }

    xx[m]=f[m][m+1]/f[m][m];
    for(int i=m-1;i>0;i--)
        xx[i]=(f[i][m+1]-f[i][i+1]*xx[i+1])/f[i][i];
    return ;
}

int main(void)
{
    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
    {
        for(int i=n-1;i>=x;i--)
        {
            f[1][1]=-2.0/3,f[1][2]=1.0/3,f[1][m+1]=-dp[i+1][1]/3-1;
            for(int j=2;j<m;j++)
            {
                f[j][j-1]=f[j][j+1]=1.0/4;
                f[j][j]=-3.0/4;
                f[j][m+1]=-dp[i+1][j]/4-1;
            }
            f[m][m-1]=1.0/3,f[m][m]=-2.0/3,f[m][m+1]=-dp[i+1][m]/3-1;

            if(m==1)
                f[1][1]=-1.0/2,f[1][2]=-dp[i+1][1]/2-1;

            Guass();
            for(int j=1;j<=m;j++)
                dp[i][j]=xx[j];
        }

        printf("%.10f\n",dp[x][y]);
    }
    return 0;
}