#include #include #include using namespace std; #define mp make_pair #define pb push_back typedef pair pii; char map[20][20]; double dp[20][20]; vector< pair > tunnelLoc; double prob(int r,int c,int n,int m, int k){ if(map[r][c] == '%') return 1; if(map[r][c] == '*') return 0; if(dp[r][c] != -1) return dp[r][c]; int moves = 4; double u = 0,d = 0, l =0, ri = 0; //checkign top if(r == 0 || map[r-1][c] == '#') moves--; else{ if(map[r-1][c] != 'T') u = prob(r-1,c,n,m,k); else{ for(int i = 0; i < k; i++){ if(tunnelLoc[i].first.first == r-1 && tunnelLoc[i].first.second == c) u = prob(tunnelLoc[i].second.first,tunnelLoc[i].second.second,n,m,k); } for(int i = 0; i < k; i++){ if(tunnelLoc[i].second.first == r-1 && tunnelLoc[i].second.second == c) u = prob(tunnelLoc[i].first.first,tunnelLoc[i].first.second,n,m,k); } } } //checking down if(r == n-1 || map[r+1][c] == '#') moves--; else{ if(map[r+1][c] != 'T') d = prob(r+1,c,n,m,k); else{ for(int i = 0; i < k; i++){ if(tunnelLoc[i].first.first == r+1 && tunnelLoc[i].first.second == c) d = prob(tunnelLoc[i].second.first,tunnelLoc[i].second.second,n,m,k); } for(int i = 0; i < k; i++){ if(tunnelLoc[i].second.first == r+1 && tunnelLoc[i].second.second == c) d = prob(tunnelLoc[i].first.first,tunnelLoc[i].first.second,n,m,k); } } } //checking left if(c == m-1 || map[r][c+1] == '#') moves--; else{ if(map[r][c+1] != 'T') l = prob(r,c+1,n,m,k); else{ for(int i = 0; i < k; i++){ if(tunnelLoc[i].first.first == r && tunnelLoc[i].first.second == c+1) l = prob(tunnelLoc[i].second.first,tunnelLoc[i].second.second,n,m,k); } for(int i = 0; i < k; i++){ if(tunnelLoc[i].second.first == r && tunnelLoc[i].second.second == c+1) l = prob(tunnelLoc[i].first.first,tunnelLoc[i].first.second,n,m,k); } } } //checking right if(c == 0 || map[r][c-1] == '#') moves--; else{ if(map[r][c-1] != 'T') ri = prob(r,c+1,n,m,k); else{ for(int i = 0; i < k; i++){ if(tunnelLoc[i].first.first == r && tunnelLoc[i].first.second == c-1) ri = prob(tunnelLoc[i].second.first,tunnelLoc[i].second.second,n,m,k); } for(int i = 0; i < k; i++){ if(tunnelLoc[i].second.first == r && tunnelLoc[i].second.second == c-1) ri = prob(tunnelLoc[i].first.first,tunnelLoc[i].first.second,n,m,k); } } } if(moves == 0){ dp[r][c] = 0; return 0; } double ans = u + d + l + ri; ans = ans / moves; dp[r][c] = ans; return ans; } int main(){ int n,m,tunnel; cin>>n>>m>>tunnel; int startRow,startCol; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin>>map[i][j]; if(map[i][j] == 'A'){ startRow = i; startCol = j; } dp[i][j] = -1; } } for(int i = 0; i < tunnel; i++){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; x1--; y1--; x2--; y2--; map[x1][y1] = 'T'; map[x2][y2] = 'T'; tunnelLoc.pb(mp(mp(x1,y1),mp(x2,y2))); } double ans = prob(startRow,startCol,n,m,tunnel); cout<