完整题面:

设f(i,j)表示路径经过(i,j)这个点的概率,列出方程消元。

但暴力消元的复杂度是$O((nm)^3)$,注意每一次消元只会影响前后m个方程,所以我们可以对于第i行,只存[i-m,i+m]这些系数来进行消元。

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

姿势水平UP~

(代码基本抄Claris的)

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

最新文章

  1. Oracle 集群】ORACLE DATABASE 11G RAC 知识图文详细教程之ORACLE集群概念和原理(二)
  2. 【MongoDB初识】-其他操作
  3. linux-----------shell的基础命令
  4. poj3696 快速幂的优化+欧拉函数+gcd的优化+互质
  5. Fiddler-009-AutoResponder 简单的 MOCK SERVER 应用实例
  6. iScroll相关
  7. Hdu3436-Queue-jumpers(伸展树)
  8. 部分GDAL工具功能简介
  9. Android 简单的图片缩放方法
  10. NAT集群部署solo之session server
  11. 十类经典office实用技巧
  12. Python笔记(二):列表+列表数据处理+函数
  13. ThreadLocal的使用[代码片段]
  14. 加密webconfig中的连接字符串,利用RSA非对称加密,利用windows保存密钥容器
  15. django后台密码错误
  16. wxpy: 用 Python 玩微信【转】
  17. 学号 20175223 《Java程序设计》第2周学习总结
  18. 3070 Fibonacci
  19. [Android App]IFCTT,即:If Copy Then That,一个基于IFTTT的&quot;This&quot;实现
  20. [TJOI2015]弦论

热门文章

  1. Flask 部署和分发
  2. $(function(){})和window.onload的区别
  3. c# BinaryWriter 和 BinaryReader
  4. Python内置函数(35)——next
  5. Jquery blokckUI 快速入门
  6. 新概念英语(1-131)Don&#39;t be so sure
  7. 大数据学习总结(6)what is our foucus
  8. maven编译时出现读取XXX时出错invalid LOC header (bad signature)
  9. bootstrap 之下拉多选
  10. 三、如何使用QtDesigner