#include #include #include #include #include #include #include #include #include #include #include using namespace std; const bool debug = false; #ifndef M_PI const double M_PI = acos(-1.0); #endif // M_PI #define y1 roman_kaban #define rank oryshych_konb #define ull unsigned long long //#define ll long long //const int mod = int(1e9) + 7; const int inf = 1e6; //const long long infLL = 1LL << 60; //const int MX2 = 10100500; // e7 //const long long INF = 1e18 + 0.5; const int MX = 6010100; // e5 const int SZ = 120; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; const int delta = 1000000; priority_queue q; double dead = 0; double ok = 0; string s[SZ]; double d[SZ][SZ]; pair a[SZ][SZ]; bool b[SZ][SZ]; double dead2 = 0; double ok2 = 0; int o; void add(int x, int y, double p){ //cerr << "ADD " << x << ' ' << y << ' ' << p << endl; if(s[x][y] == '*') { dead += p; if(o > MX / 46) dead2 += p; return; } if(s[x][y] == '%') { ok += p; if(o > MX / 46) ok2 += p; return; } d[x][y] += p; int z = delta * d[x][y]; q.push((z << 10) + (x << 5) + y); } int main() { //cout << infLL << endl; ios_base::sync_with_stdio(false); //if(debug) //freopen("/Users/melnykroman/Documents/in.txt","r", stdin); //solveC(); return 0; int n, m, k; cin >> n >> m >> k; for(int i = 0; i < n; i++){ cin >> s[i]; } while(k--){ int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; x2--; y2--; a[x1][y1] = make_pair(x2, y2); b[x1][y1] = true; swap(x1, x2); swap(y1, y2); a[x1][y1] = make_pair(x2, y2); b[x1][y1] = true; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(s[i][j] == 'A') { s[i][j] = 'O'; q.push((i << 5) + j); d[i][j] = 1; } } } for(o = 0; o < MX; o++){ //cerr << 'o'; if(q.empty()) break; int z = q.top(); q.pop(); int y = z & 31; z >>= 5; int x = z & 31; z >>= 5; int zz = d[x][y] * delta; if(zz < z) continue; //if(d[x][y] * delta + 1e-5 < z) continue; //cerr << x << ' ' << y << endl << endl; double prop = d[x][y]; d[x][y] = 0; if(b[x][y]){ // cerr << "!"; auto &temp = a[x][y]; x = temp.first; y = temp.second; } int cnt = 0; for(int i = 0; i < 4; i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] != '#') cnt++; } //cerr << cnt << endl; if(cnt == 0) {dead += prop; continue;} for(int i = 0; i < 4; i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] != '#'){ add(xx, yy, prop / cnt); } } } //ok = (ok / (dead + ok) + (ok + 1 - dead - ok)) / 2; if(dead2 + ok2 > 1e-8) ok += (1 - dead - ok) * ok2 / (dead2 + ok2); //ok /= dead + ok; printf("%.10f\n", ok); return 0; }