建立方程后直接高斯消元,再把0的区间找出来计算,就可以过(因为实际上这样的复杂度是5次的,且常数小)
(当然这样的复杂度看上去并不太好,考虑优化)
可以发现最后一行的概率都可以用上一行来表示,那么代入上一行的方程后,发现又可以再次代入,最后就求出了第一行

 1 #include<bits/stdc++.h>
2 using namespace std;
3 int t,n,m,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
4 double f[2005][2005];
5 int id(int x,int y){
6 if ((x<1)||(y<1)||(x>n)||(y>m))return 0;
7 return (x-1)*m+y;
8 }
9 double guess(){
10 for(int ii=n;ii;ii--){
11 for(int i=id(ii,1);i<=id(ii,m);i++){
12 double s=abs(f[i][i]);
13 for(int j=i+1;j<=id(ii,m);j++)s=max(s,abs(f[j][i]));
14 for(int j=i;j<=id(ii,m);j++)
15 if (s==abs(f[j][i])){
16 s=f[j][i];
17 for(int k=id(ii-1,1);k<=id(ii,m);k++)swap(f[j][k],f[i][k]);
18 swap(f[j][id(n,m)+1],f[i][id(n,m)+1]);
19 break;
20 }
21 for(int j=id(ii-1,1);j<=id(ii,m);j++)f[i][j]/=s;
22 f[i][id(n,m)+1]/=s;
23 for(int j=id(ii,1);j<=id(ii,m);j++){
24 if (j==i)continue;
25 s=f[j][i];
26 for(int k=id(ii-1,1);k<=id(ii,m);k++)f[j][k]-=f[i][k]*s;
27 f[j][id(n,m)+1]-=f[i][id(n,m)+1]*s;
28 }
29 }
30 if (ii==1)return f[1][id(n,m)+1];
31 for(int i=id(ii-1,1);i<=id(ii-1,m);i++)
32 for(int j=id(ii,1);j<=id(ii,m);j++){
33 for(int k=id(ii-1,1);k<=id(ii-1,m);k++)f[i][k]-=f[i][j]*f[j][k];
34 f[i][id(n,m)+1]-=f[i][j]*f[j][id(n,m)+1];
35 }
36 }
37 }
38 int main(){
39 while (scanf("%d%d",&n,&m)!=EOF){
40 if ((!n)&&(!m))return 0;
41 memset(f,0,sizeof(f));
42 for(int i=1;i<=n;i++)
43 for(int j=1;j<=m;j++)
44 f[id(i,j)][id(i,j)]=f[id(i,j)][id(n,m)+1]=-1;
45 for(int k=0;k<4;k++)
46 for(int i=1;i<=n;i++)
47 for(int j=1;j<=m;j++)
48 scanf("%lf",&f[id(i,j)][id(i+dx[k],j+dy[k])]);
49 f[id(n,m)][id(n,m)+1]=0;
50 printf("%.8f\n",guess());
51 }
52 }

最新文章

  1. 萌新笔记——Cardinality Estimation算法学习(二)(Linear Counting算法、最大似然估计(MLE))
  2. RHEL6.5 换源
  3. ASP.NET 2.0 异步页面原理浅析 [1]
  4. 关于python中模块的import路径
  5. 29 个 PHP 的 Excel 处理类
  6. Codeforces Round #280 (Div. 2)E Vanya and Field(简单题)
  7. longest incresing sequence
  8. float的精度,3个小数相加后精度丢失--小数比较使用bccomp()方法
  9. dubbo框架揭秘之服务引用
  10. 【bzoj3809】Gty的二逼妹子序列
  11. 【转】简单了介绍js中的一些概念(词法结构) 和 数据类型(部分)。
  12. tp5命令行基础介绍
  13. (7)linux文件常用操作命令
  14. 可以设置超时版的的fetch
  15. 实现Repeater控件的记录单选
  16. [Chrome_Error] (failed) net::ERR_INCOMPLETE_CHUNKED_ENCODING 与 nginx 502 bad gateway
  17. 基于汇编的 C/C++ 协程 - 切换上下文
  18. MikroTik RouterOS使用VirtualBox挂载物理硬盘作为虚拟机硬盘进行安装
  19. Ubuntu上CUDA环境搭建
  20. ios判断设备是iphone还是ipad

热门文章

  1. SpringCloud-SpringBoot-SpringCloudAlibaba对应版本选择
  2. Linux常用命令介绍(满足日常操作)
  3. aritest发送测试报告到邮件
  4. CentOS 文件管理
  5. Java:ThreadLocal小记
  6. MySQL:提高笔记-2
  7. OO_JAVA_JML系列作业_单元总结
  8. 「笔记」$Min\_25$筛
  9. 三极管和MOS管驱动电路的正确用法
  10. ssh key公钥