I understand the entire solution except the part " The probability of reaching any particular green square is the same for all but the green square in the last row", I don't get it why the last row is any different?
My understanding of the solution : We take all the squares which the extension of the diaganol of the rectangle part. We have to pass through one of these squares in order to reach the destination. Since there can be interesction between these paths, we individually find the probability of reaching each of these squares and add them.
Can anyone please explain how the last row is any different?
My code :
` //IF YOU GIVE UP,THEN YOU DON'T DESERVE IT
include<bits/stdc++.h>
define ll long long
define pii pair<int,int>
define pll pair<long long,long long>
define pb push_back
define endl "\n"
define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
define PI 3.14159265358979323846264
define isz(x) (int)x.size()
using namespace std;
include <ext/pb_ds/assoc_container.hpp>
include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
define typ int
define ordered_set tree<typ, null_type, less, rb_tree_tag, tree_order_statistics_node_update>
//*s.find_by_order(x) --> value at position x(0-indexed) //s.order_of_key(x) --> number of elements less than x
define eps 1e-9
define maxn 100005
double lfact[maxn]; ll w,h,l,u,r,d;
// find probability to reach sqaure (m,n) from (1,1) double find_prob(ll m, ll n) { ll u = m+n-2;
double res = lfact[u] - lfact[n-1] - lfact[u-n+1]-(u*log(2)); return exp(res);
}
double solve(ll w,ll h,ll l,ll u,ll r,ll d) {
// deal squares below y = x line int cr = d; int cc = l; cr++;cc--; double ans = 0.0;
while(cc>0 and cr<=h) { ans+=find_prob(cr,cc); cc--;cr++; }
// deal squares above y = x line cr = u; cc = r; cc++;cr--; while(cc<=w and cr>0) { ans+=find_prob(cr,cc); cr--;cc++; } return ans;
}
main() { int t; cin>>t; int tt = t; lfact[0] = 0.0; for(int i=1;i<=100000;i++) lfact[i] = lfact[i-1] + log(i);
while(t--) { cin>>w>>h>>l>>u>>r>>d; double ans = solve(w,h,l,u,r,d); cout<<"Case #"<<tt-t<<": "<<setprecision(9)<<ans<<endl; }
}
`