列出$n\times m$个未知量、$n\times m$个方程的方程组进行高斯消元。

注意到每次消元时只会影响前后$m$个方程，故只保存增广矩阵中的这些项，同时只对这些项进行消元即可。

时间复杂度$O(nm^3)$。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int N=10010,M=23;const double eps=1e-12;int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};int n,m,i,j,k,x,y,o,l,r,cnt,pos[N*M],v[N*M];double p[4],t,a[N*M][M*2],g[N*M];char s[N][M];inline double&f(int x,int y){return a[x][x-y+M];}int main(){  scanf("%d%d",&m,&n);  for(i=0;i<4;i++)scanf("%lf",&p[i]),p[i]/=100;  for(i=0;i
        
         =n||y<0||y>=m||s[x][y]=='X')f(o,o)-=p[k];      else if(s[x][y]=='.')f(o,x*m+y)-=p[k^1];    }    if(s[i][j]=='T')f(o,o)=1;  }  for(i=0;i
         
          eps){k=j;break;}    if(k<0){pos[i]=-1;continue;}    v[pos[i]=k]=1;    for(j=k+1;j<=r;j++){      t=f(j,i)/f(k,i);      for(x=i;x
          
           <=k+m;x++)f(j,x)-=f(k,x)*t; g[j]-=g[k]*t; } } for(i=n*m-1;~i;i--)if(~pos[i]){ k=pos[i],l=max(0,i-m),r=min(n*m-1,i+m); for(j=l;j<=r;j++)if(j!=k)g[k]-=f(k,j)*g[j]; g[k]/=f(k,i); } for(i=0;i