HDU-2262 Where is the canteen確率DP,Gauss消元
25750 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2262
标题:LLは迷路の中を回っていて、周りに歩ける点に向かう確率は毎回同じで、今LLはランダムにcanteenのどこまで歩いて、期待を求めます.
これはバンドリングの期待を求める問題であり,特別性はなく,方程式をリストし,gauss消元するしかない.まずBFSで歩ける点を求め,canteenまで歩けるか否かを判断する.次に、所望の方程式を列挙し、E[i]=Σ( E[j]*p[j] ) +1.それからよく求めて、テーマの中で多くのcanteenに注意します...
标题:LLは迷路の中を回っていて、周りに歩ける点に向かう確率は毎回同じで、今LLはランダムにcanteenのどこまで歩いて、期待を求めます.
これはバンドリングの期待を求める問題であり,特別性はなく,方程式をリストし,gauss消元するしかない.まずBFSで歩ける点を求め,canteenまで歩けるか否かを判断する.次に、所望の方程式を列挙し、E[i]=Σ( E[j]*p[j] ) +1.それからよく求めて、テーマの中で多くのcanteenに注意します...
1 //STATUS:C++_AC_437MS_700KB
2 #include <functional>
3 #include <algorithm>
4 #include <iostream>
5 //#include <ext/rope>
6 #include <fstream>
7 #include <sstream>
8 #include <iomanip>
9 #include <numeric>
10 #include <cstring>
11 #include <cassert>
12 #include <cstdio>
13 #include <string>
14 #include <vector>
15 #include <bitset>
16 #include <queue>
17 #include <stack>
18 #include <cmath>
19 #include <ctime>
20 #include <list>
21 #include <set>
22 #include <map>
23 using namespace std;
24 //#pragma comment(linker,"/STACK:102400000,102400000")
25 //using namespace __gnu_cxx;
26 //define
27 #define pii pair<int,int>
28 #define mem(a,b) memset(a,b,sizeof(a))
29 #define lson l,mid,rt<<1
30 #define rson mid+1,r,rt<<1|1
31 #define PI acos(-1.0)
32 //typedef
33 typedef __int64 LL;
34 typedef unsigned __int64 ULL;
35 //const
36 const int N=230;
37 const int INF=0x3f3f3f3f;
38 const LL MOD=1000000007,STA=8000010;
39 const LL LNF=1LL<<55;
40 const double EPS=1e-9;
41 const double OO=1e30;
42 const int dx[4]={-1,0,1,0};
43 const int dy[4]={0,1,0,-1};
44 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
45 //Daily Use ...
46 inline int sign(double x){return (x>EPS)-(x<-EPS);}
47 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
48 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
49 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
50 template<class T> inline T Min(T a,T b){return a<b?a:b;}
51 template<class T> inline T Max(T a,T b){return a>b?a:b;}
52 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
53 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
54 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
55 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
56 //End
57
58 /* gauss_elimination O(n^3)
59 n n
60
61 A[][] , A[i][n] i bi
62 A[i][n] i */
63 int vis[20][20],cnt[20][20],e[20][20];
64 char g[20][20];
65 int n,m,tot,sx,sy;
66
67 double A[N][N];
68
69 int gauss(int n)
70 {
71 int i,j,k,r;
72 for(i=0;i<n;i++){
73 // r i ，
74 r=i;
75 for(j=i+1;j<n;j++)
76 if(fabs(A[j][i]) > fabs(A[r][i]))r=j;
77 if(r!=i)for(j=0;j<=n;j++)swap(A[r][j],A[i][j]);
78 //i i+1~n
79 /* for(k=i+1;k<n;k++){ // ， f
80 double f=A[k][i]/A[i][i];
81 for(j=i;j<=n;j++)A[k][j]-=f*A[i][j];
82 }*/
83 for(j=n;j>=i;j--){ // ，
84 for(k=i+1;k<n;k++)
85 A[k][j]-=A[k][i]/A[i][i]*A[i][j];
86 }
87 }
88 //
89 for(i=0;i<n;i++)if(sign(A[i][i])==0)return 0;
90 //
91 for(i=n-1;i>=0;i--){
92 for(j=i+1;j<n;j++)
93 A[i][n]-=A[j][n]*A[i][j];
94 A[i][n]/=A[i][i];
95 }
96 return 1;
97 }
98
99 int bfs()
100 {
101 int i,j,x,y,nx,ny,t;
102 queue<int> q;
103 q.push(sx*m+sy);
104 mem(vis,-1);mem(cnt,0);
105 vis[sx][sy]=tot=0;
106 tot++;
107 while(!q.empty()){
108 t=q.front();q.pop();
109 x=t/m;y=t%m;
110 for(i=0;i<4;i++){
111 nx=x+dx[i];
112 ny=y+dy[i];
113 if(nx>=0&&nx<n && ny>=0&&ny<m && g[nx][ny]!='#'){
114 cnt[x][y]++;
115 if(vis[nx][ny]!=-1)continue;
116 vis[nx][ny]=tot++;
117 q.push(nx*m+ny);
118 }
119 }
120 }
121 for(i=0;i<n;i++){
122 for(j=0;j<m;j++)
123 if(vis[i][j]!=-1 && e[i][j])return 1;
124 }
125 return 0;
126 }
127
128 int main(){
129 // freopen("in.txt","r",stdin);
130 int i,j,k;
131 while(~scanf("%d%d",&n,&m))
132 {
133 mem(e,0);
134 for(i=0;i<n;i++){
135 scanf("%s",g[i]);
136 for(j=0;j<m;j++){
137 if(g[i][j]=='@')sx=i,sy=j;
138 else if(g[i][j]=='$')e[i][j]=1;
139 }
140 }
141
142 if(!bfs()){
143 printf("-1
");
144 continue;
145 }
146 mem(A,0);
147 for(i=0;i<n;i++){
148 for(j=0;j<m;j++){
149 if(vis[i][j]==-1)continue;
150 int u=vis[i][j];
151 double p=1.0/cnt[i][j];
152 if(e[i][j]){
153 A[u][u]=1;
154 A[u][tot]=0;
155 continue;
156 }
157 A[u][u]=A[u][tot]=1;
158 for(k=0;k<4;k++){
159 int x=i+dx[k],y=j+dy[k];
160 if(x>=0&&x<n && y>=0&&y<m && vis[x][y]!=-1){
161 A[u][vis[x][y]]=-p;
162 }
163 }
164 }
165 }
166 gauss(tot);
167 printf("%.6lf
",A[vis[sx][sy]][tot]);
168 }
169 return 0;
170 }