/* "Why do we fall? So we can learn how to pick ourselves up." - Alfred, Batman Begins - */ # include # include # include # include # include # include # include # include # include # include # include # define mp make_pair # define LL long long # define vi vector # define pqu priority_queue # define iasc int,vector,greater # define LLasc LL,vector,greater # define ins push_back # define pii pair # define fi first # define se second inline void in(int &MAGNUS) {scanf("%d",&MAGNUS);} inline void out(int MAGNUS) {printf("%d\n",MAGNUS);} inline void in(int &MAGNUS,int &CLAR) {scanf("%d%d",&MAGNUS,&CLAR);} inline void out(int MAGNUS,int CLAR) {printf("%d %d\n",MAGNUS,CLAR);} inline void inl(LL &LIV) {scanf("%lld",&LIV);} inline void inl(LL &LIV,LL &MART) {scanf("%lld%lld",&LIV,&MART);} inline void outl(LL LIV) {printf("%lld\n",LIV);} inline void outl(LL LIV, LL MART) {printf("%lld %lld\n",LIV,MART);} # define FORU(a,b,c) for(int a=b; a<=c; a++) # define FORD(a,b,c) for(int a=b; a>=c; a--) # define FOR(a,b) for(int a=1; a<=b; a++) # define FORA(a,b) for(auto (a) : (b)) # define REP(a,b) for(int a=0; a> m[i][j]; if(m[i][j]=='A') sr=i, sc=j; } FOR(k,K){ int r1,c1,r2,c2; in(r1,c1); in(r2,c2); tunnel[r1][c1]=tunnel[r2][c2]=1; if(loop(r1,c1) || loop(r2,c2)){ printf("%.6lf\n",0); return 0; } warp[r1][c1]=mp(r2,c2); warp[r2][c2]=mp(r1,c1); } int bom=0, done=0, trap=0; queue q; q.push(mp(sr,sc)); while(!q.empty()){ pii state=q.front(); q.pop(); int r=state.fi, c=state.se; vis[r][c]=1; int allwall=1; FORU(i,0,3){ int nxr=r+dx[i]; int nxc=c+dy[i]; if(!inside(nxr,nxc)) continue; if(m[nxr][nxc]=='%') allwall=0,done++; else if(m[nxr][nxc]=='*') allwall=0,bom++; else if(m[nxr][nxc]=='O'){ pii nex=warp[nxr][nxc]; allwall=0; if(vis[nex.fi][nex.se]) continue; q.push(nex); } } if(allwall) trap++; } printf("%.6lf\n",done/(double)(done+bom+trap)); return 0; }