Alef the Frog is in an $n\times m$ two-dimensional maze represented as a table.  The maze has the following characteristics: 

Each cell can be free or can contain an obstacle, an exit, or a mine.
Any two cells in the table considered adjacent if they share a side.  
The maze is surrounded by a solid wall made of obstacles. 
Some pairs of free cells are connected by a bidirectional tunnel. 

When Alef is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don't contain an obstacle in it. If this cell contains a mine, the mine explodes and Alef dies. If this cell contains an exit, then Alef escapes the maze.  

When Alef lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won't fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)   

It's possible for Alef to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.  

Your task is to write a program which calculates and prints a probability that Alef escapes the maze.

Input Format

The first line contains three space-separated integers $n$, $m$ and $\boldsymbol{\mbox{k}}$ denoting the dimensions of the maze and the number of bidirectional tunnels.  

The next $n$ lines describe the maze. The $\boldsymbol{i}$'th line contains a string of length $m$ denoting the $\boldsymbol{i}$'th row of the maze. The meaning of each character is as follows:

# denotes an obstacle.
A denotes a free cell where Alef is initially in.  
* denotes a cell with a mine. 
% denotes a cell with an exit.  
O denotes a free cell (which may contain an entrance to a tunnel).  

The next $\boldsymbol{\mbox{k}}$ lines describe the tunnels. The $\boldsymbol{i}$'th line contains four space-separated integers $\boldsymbol{i_1}$, $j_1$, $i_2$, $j_2$. Here, $(i_1,j_1)$ and $(i_2,j_2)$ denote the coordinates of both entrances of the tunnel. $(i,j)$ denotes the row and column number, respectively.  

Constraints

$1\leq n,m\leq20$
$0\leq2\cdot k\leq n\cdot m$  
$1\leq i_1,i_2\leq n$  
$1\leq j_1,j_2\leq m$  
$(i_1,j_1)$ and $(i_2,j_2)$ are distinct.  
A appears exactly once.  
Each free cell contains at most one entrance to a tunnel.  
If a cell contains an entrance to a tunnel, then it doesn't contain an obstacle, mine or exit, and Alef doesn't initially stand in it.
Tunnels don't connect adjacent cells.

Output Format

Print one real number denoting the probability that Alef escapes the maze. Your answer will be considered to be correct if its (absolute) difference from the true answer is not greater than $\mathbf{10^{-6}}$.  

Sample Input 0
3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

Sample Output 0
0.25

Explanation 0

The following depicts this sample case:

In this case, Alef will randomly choose one of four adjacent cells. If he goes up or down, he will explode and die. If he goes right, he will escape. If he goes left, he will go through a tunnel and get stuck in cell $(2,1)$. So the probability of Alef escaping is $\frac{1}{4}$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import sys
sys.setrecursionlimit(10001)
obstacle = '#'
start = 'A'
mine = '*'
exitcode = '%'
freecell = 'O'
tunnel = 'T'
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
maze = {}
for i in range(n):
	row = input().strip()
	for j in range(m):
		maze[i, j] = row[j]
		if maze[i, j] == start:
			alef_start = (i, j)
			maze[i, j] = freecell
tunnels = {}
for i in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1) - 1, int(j1) - 1, int(i2) - 1, int(j2) - 1]
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
	maze[i1, j1] = tunnel
	maze[i2, j2] = tunnel

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def get_valid_adjacent_cells(p):
	(i, j) = p
	adj = []
	if i > 0 and maze[i - 1, j] != obstacle:
		adj.append((i - 1, j))
	if i < n - 1 and maze[i + 1, j] != obstacle:
		adj.append((i + 1, j))
	if j > 0 and maze[i, j - 1] != obstacle:
		adj.append((i, j - 1))
	if j < m - 1 and maze[i, j + 1] != obstacle:
		adj.append((i, j + 1))
	return adj

def index(p):
	return m * p[0] + p[1]
mat = [[0 for j in range(n * m + 1)] for i in range(n * m)]
for i in range(n * m):
	mat[i][i] = 1
queue = [alef_start]
num_exits = 0
while queue:
	pos = queue.pop(0)
	i = index(pos)
	if mat[i][i] == -1:
		continue
	mat[i][i] = -1
	if maze[pos] == mine:
		continue
	if maze[pos] == exitcode:
		mat[i][n * m] = -1
		num_exits += 1
		continue
	adj_cells = get_valid_adjacent_cells(pos)
	num_adj_cells = len(adj_cells)
	if num_adj_cells == 0:
		continue
	for c in adj_cells:
		if maze[c] == tunnel:
			mat[i][index(tunnels[c])] = 1.0 / num_adj_cells
			queue.append(tunnels[c])
		else:
			mat[i][index(c)] = 1.0 / num_adj_cells
			queue.append(c)
if num_exits == 0:
	print(0)
else:
	x = gauss(mat)
	print(x[index(alef_start)])


import sys
M = list()
tunnel = dict()
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
for a0 in range(n):
	M.append(input())
for a0 in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1), int(j1), int(i2), int(j2)]
	tunnel[i1 - 1, j1 - 1] = (i2 - 1, j2 - 1)
	tunnel[i2 - 1, j2 - 1] = (i1 - 1, j1 - 1)

def getNeighbours(i, j):
	result = []
	for (k, l) in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
		if k < 0 or k >= n or l < 0 or (l >= m) or (M[k][l] == '#'):
			continue
		if (k, l) in tunnel:
			(k, l) = tunnel[k, l]
		result.append((k, l))
	return result

def markReachable(reachable, i, j):
	if reachable[i][j]:
		return
	reachable[i][j] = 1
	neigh = getNeighbours(i, j)
	for (k, l) in neigh:
		markReachable(reachable, k, l)
for i in range(n):
	for j in range(m):
		if M[i][j] == 'A':
			frog_position = (i, j)
reachable = [[0 for j in range(m)] for i in range(n)]
(i, j) = frog_position
markReachable(reachable, i, j)
R = [[float(i == j) for j in range(n * m)] for i in range(n * m)]
b = [0.0 for i in range(n * m)]
for i in range(0, n):
	for j in range(0, m):
		if M[i][j] == '%':
			b[i * m + j] = 1.0
		if M[i][j] == 'A' or (M[i][j] == 'O' and reachable[i][j]):
			neigh = getNeighbours(i, j)
			for (k, l) in neigh:
				R[i * m + j][k * m + l] = -1 / len(neigh)

def gaussian_elimination(A, b):
	n = len(A)
	for i in range(0, n):
		max_value = abs(A[i][i])
		max_row = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > max_value:
				max_value = abs(A[k][i])
				max_row = k
		for k in range(i, n):
			tmp = A[max_row][k]
			A[max_row][k] = A[i][k]
			A[i][k] = tmp
		tmp = b[max_row]
		b[max_row] = b[i]
		b[i] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			b[k] += c * b[i]
			for j in range(i, n):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]

def solve_leq(A, b):
	gaussian_elimination(A, b)
	n = len(A)
	for i in range(n - 1, -1, -1):
		b[i] = b[i] / A[i][i]
		for k in range(i - 1, -1, -1):
			b[k] -= A[k][i] * b[i]
solve_leq(R, b)
(i, j) = frog_position
print(b[i * m + j])


def load_problem():
	(n, m, k) = map(int, input().split())
	grid = []
	active = []
	for i in range(n):
		line = input().strip()
		assert len(line) == m
		grid.append(line)
		j = line.find('A')
		if j >= 0:
			active.append((i, j))
	assert len(active) == 1
	tunnel = {}
	for i in range(k):
		(i1, j1, i2, j2) = map(int, input().split())
		p1 = (i1 - 1, j1 - 1)
		p2 = (i2 - 1, j2 - 1)
		tunnel[p1] = p2
		tunnel[p2] = p1
	seen = {active[0]: 0}
	jumps = [None]
	while active:
		p = active.pop()
		(i, j) = p
		jump = []
		jumps[seen[p]] = jump
		for (i2, j2) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
			if i2 < 0 or i2 >= n or j2 < 0 or (j2 >= m):
				continue
			sq = grid[i2][j2]
			if sq == '#':
				continue
			elif sq == '*':
				jump.append(-1)
			elif sq == '%':
				jump.append(-2)
			elif sq == 'O' or sq == 'A':
				p2 = (i2, j2)
				if p2 in tunnel:
					p2 = tunnel[p2]
				if p2 not in seen:
					seen[p2] = len(jumps)
					jumps.append(None)
					active.append(p2)
				jump.append(seen[p2])
			else:
				assert 0
		if not jump:
			jump.append(-1)
	return jumps

def solve_mat(jumps):
	can_escape = 0
	can_explode = 0
	size = len(jumps)
	mat = []
	for i in range(size):
		row = [0.0] * (size + 2)
		row[i] = 1.0
		mat.append(row)
		p = 1 / len(jumps[i])
		for j in jumps[i]:
			if j >= 0:
				row[j] -= p
			elif j == -1:
				row[size + 1] += p
				can_explode = 1
			elif j == -2:
				row[size] += p
				can_escape = 1
	if not can_escape:
		return 0.0
	if not can_explode:
		return 1.0
	for i in range(size):
		p = i
		x = abs(mat[i][i])
		for j in range(i + 1, size):
			y = abs(mat[j][i])
			if y > x:
				x = y
				p = j
		assert x > 1e-06
		if i != p:
			(mat[i], mat[p]) = (mat[p], mat[i])
		row = mat[i]
		x = row[i]
		row[i] = 1.0
		for j in range(i + 1, size + 2):
			row[j] /= x
		for j in range(size):
			y = mat[j][i]
			if j == i or y == 0.0:
				continue
			mat[j][i] = 0.0
			for k in range(i + 1, size + 2):
				mat[j][k] -= row[k] * y
	return mat[0][size]
jumps = load_problem()
print(solve_mat(jumps))


import sys
sys.setrecursionlimit(10001)
obstacle = '#'
start = 'A'
mine = '*'
exitcode = '%'
freecell = 'O'
tunnel = 'T'
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
maze = {}
for i in range(n):
	row = input().strip()
	for j in range(m):
		maze[i, j] = row[j]
		if maze[i, j] == start:
			alef_start = (i, j)
			maze[i, j] = freecell
tunnels = {}
for i in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1) - 1, int(j1) - 1, int(i2) - 1, int(j2) - 1]
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
	maze[i1, j1] = tunnel
	maze[i2, j2] = tunnel

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def get_valid_adjacent_cells(p):
	(i, j) = p
	adj = []
	if i > 0 and maze[i - 1, j] != obstacle:
		adj.append((i - 1, j))
	if i < n - 1 and maze[i + 1, j] != obstacle:
		adj.append((i + 1, j))
	if j > 0 and maze[i, j - 1] != obstacle:
		adj.append((i, j - 1))
	if j < m - 1 and maze[i, j + 1] != obstacle:
		adj.append((i, j + 1))
	return adj

def index(p):
	return m * p[0] + p[1]
mat = [[0 for j in range(n * m + 1)] for i in range(n * m)]
for i in range(n * m):
	mat[i][i] = 1
queue = [alef_start]
num_exits = 0
while queue:
	pos = queue.pop(0)
	i = index(pos)
	if mat[i][i] == -1:
		continue
	mat[i][i] = -1
	if maze[pos] == mine:
		continue
	if maze[pos] == exitcode:
		mat[i][n * m] = -1
		num_exits += 1
		continue
	adj_cells = get_valid_adjacent_cells(pos)
	num_adj_cells = len(adj_cells)
	if num_adj_cells == 0:
		continue
	for c in adj_cells:
		if maze[c] == tunnel:
			mat[i][index(tunnels[c])] = 1.0 / num_adj_cells
			queue.append(tunnels[c])
		else:
			mat[i][index(c)] = 1.0 / num_adj_cells
			queue.append(c)
if num_exits == 0:
	print(0)
else:
	x = gauss(mat)
	print(x[index(alef_start)])


import sys
(n, m, k) = [int(i) for i in input().split()]
n_itr = [input() for i in range(n)]
tunel = {}
for _ in range(k):
	tun = list(map(int, input().split()))
	tunel[tun[0] - 1, tun[1] - 1] = (tun[2] - 1, tun[3] - 1)
	tunel[tun[2] - 1, tun[3] - 1] = (tun[0] - 1, tun[1] - 1)
mapa = {}
visited = {}
for i in range(n):
	for j in range(m):
		mapa[i, j] = n_itr[i][j]
		visited[i, j] = 0
		if n_itr[i][j] == 'A':
			mapa[i, j] = 'O'
			alef = (i, j)
matrix = [0 for i in range(n * m + 1)]

def neighbour(pos):
	possibles = []
	(i, j) = pos
	for (k, l) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
		if k < 0 or k >= n or l < 0 or (l >= m) or (mapa[k, l] == '#'):
			continue
		else:
			if (k, l) in tunel:
				(k, l) = tunel[k, l]
			possibles.append((k, l))
	return possibles

def index(pos):
	(x, y) = pos
	return x * m + y
Q = alef[:]
markov = [[1 if i == j else 0 for i in range(n * m + 1)] for j in range(n * m)]

def build_Markov():
	exits = 0
	Q = []
	Q.append(alef)
	while Q:
		pos = Q.pop()
		ind = index(pos)
		if visited[pos] == 1 or mapa[pos] == '*':
			continue
		visited[pos] = 1
		if mapa[pos] == '%':
			exits += 1
			markov[ind][-1] = 1
			continue
		neigh = neighbour(pos)
		if neigh == 0:
			continue
		for i in neigh:
			markov[ind][index(i)] = -1 / len(neigh)
			Q.append(i)
	return markov
markov = build_Markov()

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x
print(gauss(markov)[index(alef)])


import math
import os
import random
import re
import sys
OFFSET = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def possible(maze, i, j, n, m):
	return not (i < 0 or j < 0 or i >= n or (j >= m) or (maze[i][j] == '#'))

def dead_end(maze, i, j, n, m):
	if maze[i][j] == '*':
		return True
	for d in OFFSET:
		new_i = i + d[0]
		new_j = j + d[1]
		if possible(maze, new_i, new_j, n, m):
			return False
	return True

def dfs(maze, i, j, tunnels, n, m, var):
	if maze[i][j] == '%':
		return (1, 0)
	if dead_end(maze, i, j, n, m):
		return (0, 1)
	(exits, dead_ends) = (0, 0)
	(total, goods, bads) = ([], [], [])
	for d in OFFSET:
		new_i = i + d[0]
		new_j = j + d[1]
		if possible(maze, new_i, new_j, n, m):
			if (new_i, new_j) in tunnels:
				maze[new_i][new_j] = 't'
				(new_i, new_j) = tunnels[new_i, new_j]
			v = (new_i, new_j)
			total.append(v)
			if maze[new_i][new_j] == '%':
				goods.append(v)
			if dead_end(maze, new_i, new_j, n, m):
				bads.append(v)
			if maze[new_i][new_j] != '!':
				if maze[i][j] == 'O':
					maze[i][j] = '!'
				if maze[i][j] == 't':
					maze[i][j] = '!'
				(e, d) = dfs(maze, new_i, new_j, tunnels, n, m, var)
				exits += e
				dead_ends += d
	var[i, j] = [total, goods, bads]
	return (exits, dead_ends)

def find_alef(maze, n, m):
	for i in range(n):
		for j in range(m):
			if maze[i][j] == 'A':
				maze[i][j] = '!'
				return (i, j)

def get_indexs(dic, i, j):
	d = dict()
	idc = 1
	for key in dic.keys():
		if key == (i, j):
			d[key] = 0
		else:
			d[key] = idc
			idc += 1
	return d

def build_matrix_for_gauss(dic, i, j):
	n = len(dic)
	m = []
	idx = get_indexs(dic, i, j)
	for (key, values) in sorted(dic.items(), key=lambda item: idx[item[0]]):
		line = [0] * (n + 1)
		idi = idx[key]
		line[idi] = -1
		line[-1] = -(len(values[1]) / len(values[0]))
		for neibs in set(values[0]) - set(values[1]) - set(values[2]):
			idi = idx[neibs]
			line[idi] = 1 / len(values[0])
		m.append(line)
	return m

def calc(maze, tunnels, n, m):
	(i, j) = find_alef(maze, n, m)
	variables = dict()
	(exits, dead_ends) = dfs(maze, i, j, tunnels, n, m, variables)
	if exits == 0:
		return 0
	a = build_matrix_for_gauss(variables, i, j)
	result = gauss(a)
	return result[0]
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
maze = []
for n_itr in range(n):
	row = list(input())
	maze.append(row)
tunnels = dict()
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0]) - 1
	j1 = int(i1J1I2J2[1]) - 1
	i2 = int(i1J1I2J2[2]) - 1
	j2 = int(i1J1I2J2[3]) - 1
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
print(calc(maze, tunnels, n, m))


import sys
from collections import deque
import math

def get_node(nodes, name):
	node = [node for node in nodes if node.name == name]
	if node:
		return node[0]
	else:
		return None

class DirectedEdge:

	def __init__(self, start_node, end_node, weight):
		self.start_node = start_node
		self.end_node = end_node
		self.weight = weight

	@property
	def name(self):
		return self.start_node.name + '_' + self.end_node.name

	def has_node(self, node):
		return self.start_node == node or self.end_node == end_node

	def __eq__(self, other):
		return self.start_node == other.start_node and self.end_node == other.end_node

	def __str__(self):
		return self.name

class Node:

	def __init__(self, name, node_type, value):
		self.name = name
		self.type = node_type
		self.edges_in = dict()
		self.edges_out = dict()

	def rekey_edges(self):
		new_edges_out = dict()
		new_edges_in = dict()
		for (k, edge) in self.edges_out.items():
			new_edges_out[edge.name] = edge
		for (k, edge) in self.edges_in.items():
			new_edges_in[edge.name] = edge
		self.edges_in = new_edges_in
		self.edges_out = new_edges_out

	def balance_weight_out(self):
		sum_weight = 0
		for (k, edge) in self.edges_out.items():
			sum_weight += edge.weight
		for (k, edge) in self.edges_out.items():
			edge.weight = edge.weight / sum_weight

	@classmethod
	def add_edge(cls, start_node, end_node, weight=1):
		new_edge = DirectedEdge(start_node, end_node, weight)
		edge_in_start = str(new_edge) in start_node.edges_out
		edge_in_end = str(new_edge) in end_node.edges_in
		if edge_in_start and (not edge_in_end) or (edge_in_end and (not edge_in_start)):
			raise ValueError('Edge should exist in both start and end node.' + ' edge_in_start: ' + start_node.name + ' ' + str(edge_in_start) + ' edge_in_end: ' + end_node.name + ' ' + str(edge_in_end))
		elif edge_in_start and edge_in_end:
			existing_edge = start_node.edges_out[str(new_edge)]
			existing_edge.weight += weight
		else:
			start_node.edges_out[str(new_edge)] = new_edge
			end_node.edges_in[str(new_edge)] = new_edge

	@classmethod
	def collapse(cls, node):
		edges_out = node.edges_out
		edges_in = node.edges_in
		for (k, edge_in) in edges_in.items():
			in_node = edge_in.start_node
			edge_in_weight = edge_in.weight
			for (k, edge_out) in edges_out.items():
				out_node = edge_out.end_node
				if in_node != out_node:
					new_weight = edge_in.weight * edge_out.weight
					Node.add_edge(in_node, out_node, new_weight)
		for (k, edge_in) in edges_in.items():
			in_node = edge_in.start_node
			del in_node.edges_out[str(edge_in)]
			in_node.balance_weight_out()
		for (k, edge_out) in edges_out.items():
			out_node = edge_out.end_node
			del out_node.edges_in[str(edge_out)]
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
nodes = []
exit_nodes = []
grid = []
for a0 in range(n):
	row = input().strip()
	row = list(row)
	grid_row = []
	for (i, cell) in enumerate(row):
		node = None
		value = 0
		cell_name = str(a0) + '_' + str(i)
		if cell == '#':
			grid_row.append(None)
			continue
		elif cell == '%':
			cell_type = 'Exit'
		elif cell == '*':
			cell_type = 'Mine'
		elif cell == 'O':
			cell_type = 'Free'
		elif cell == 'A':
			cell_type = 'Start'
			value = 1
		else:
			raise ValueError('Invalid input')
		node = Node(cell_name, cell_type, value)
		if cell_type == 'Exit':
			exit_nodes.append(node)
		nodes.append(node)
		grid_row.append(node)
	grid.append(grid_row)
for i in range(0, n):
	for j in range(0, m):
		if i != 0:
			if grid[i][j] is not None and grid[i - 1][j] is not None:
				if grid[i][j].type not in ['Exit', 'Mine']:
					Node.add_edge(grid[i][j], grid[i - 1][j])
				if grid[i - 1][j].type not in ['Exit', 'Mine']:
					Node.add_edge(grid[i - 1][j], grid[i][j])
		if j != 0:
			if grid[i][j] is not None and grid[i][j - 1] is not None:
				if grid[i][j].type not in ['Exit', 'Mine']:
					Node.add_edge(grid[i][j], grid[i][j - 1])
				if grid[i][j - 1].type not in ['Exit', 'Mine']:
					Node.add_edge(grid[i][j - 1], grid[i][j])
for a0 in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1), int(j1), int(i2), int(j2)]
	a = grid[i1 - 1][j1 - 1]
	b = grid[i2 - 1][j2 - 1]
	a_out = a.edges_out.items()
	for (k, edge) in a_out:
		edge.start_node = b
	b_out = b.edges_out.items()
	for (k, edge) in b_out:
		edge.start_node = a
	(a.edges_out, b.edges_out) = (b.edges_out, a.edges_out)
sink_nodes = []
for node in nodes:
	if len(node.edges_out) == 0 and node.type != 'Exit':
		node.type = 'Sink'
		sink_nodes.append(node)
for node in nodes:
	node.balance_weight_out()
	node.rekey_edges()
for node in nodes:
	if node.type == 'Free':
		Node.collapse(node)
nodes = [node for node in nodes if node.type != 'Free']
start_nodes = [node for node in nodes if node.type == 'Start']
if start_nodes:
	start_node = start_nodes[0]
	total = 0
	for (k, edge) in start_node.edges_out.items():
		if edge.end_node.type == 'Exit':
			total += edge.weight
	print(total)
else:
	print(0)


import math
import os
import random
import re
import sys

def load_game():
	nmk = input().split()
	n = int(nmk[0])
	m = int(nmk[1])
	k = int(nmk[2])
	grid = []
	active = []
	for n_itr in range(n):
		row = input().strip()
		assert len(row) == m
		grid.append(row)
		j = row.find('A')
		if j >= 0:
			active.append((n_itr, j))
	assert len(active) == 1
	tunnel = {}
	for k_itr in range(k):
		(i1, j1, i2, j2) = map(int, input().split())
		p1 = (i1 - 1, j1 - 1)
		p2 = (i2 - 1, j2 - 1)
		tunnel[p1] = p2
		tunnel[p2] = p1
	seen = {active[0]: 0}
	jumps = [None]
	while active:
		p = active.pop()
		(i, j) = p
		jump = []
		jumps[seen[p]] = jump
		for (i2, j2) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
			if i2 < 0 or i2 >= n or j2 < 0 or (j2 >= m):
				continue
			sq = grid[i2][j2]
			if sq == '#':
				continue
			elif sq == '*':
				jump.append(-1)
			elif sq == '%':
				jump.append(-2)
			elif sq == 'O' or sq == 'A':
				p2 = (i2, j2)
				if p2 in tunnel:
					p2 = tunnel[p2]
				if p2 not in seen:
					seen[p2] = len(jumps)
					jumps.append(None)
					active.append(p2)
				jump.append(seen[p2])
			else:
				assert 0
		if not jump:
			jump.append(-1)
	return jumps

def comput_prob(jumps):
	can_escape = 0
	can_explode = 0
	mat = []
	size = len(jumps)
	for i in range(size):
		row = [0.0] * (size + 2)
		row[i] = 1.0
		mat.append(row)
		p = 1 / len(jumps[i])
		for j in jumps[i]:
			if j >= 0:
				row[j] -= p
			elif j == -1:
				row[size + 1] += p
				can_explode = 1
			elif j == -2:
				row[size] += p
				can_escape = 1
	if not can_escape:
		return 0.0
	if not can_explode:
		return 1.0
	for i in range(size):
		p = i
		x = abs(mat[i][i])
		for j in range(i + 1, size):
			y = abs(mat[j][i])
			if y > x:
				x = y
				p = j
		assert x > 1e-06
		if i != p:
			(mat[i], mat[p]) = (mat[p], mat[i])
		row = mat[i]
		x = row[i]
		row[i] = 1.0
		for j in range(i + 1, size + 2):
			row[j] /= x
		for j in range(size):
			y = mat[j][i]
			if j == i or y == 0.0:
				continue
			mat[j][i] = 0.0
			for k in range(i + 1, size + 2):
				mat[j][k] -= row[k] * y
	return mat[0][size]
jumps = load_game()
print(comput_prob(jumps))


import math
import os
import random
import re
import sys
from collections import deque

def toTunnels(tunnels, p):
	for (t1, t2) in tunnels:
		if t1 == p:
			return t2
		if t2 == p:
			return t1
	return p

def getPath(maze, tunnels):
	(n, m) = (len(maze), len(maze[0]))
	queue = deque()
	res = []
	visited = [[0 for j in range(m)] for i in range(n)]
	for i in range(n):
		for j in range(m):
			if maze[i][j] == '%':
				queue.append((i, j))
				visited[i][j] = 1
	while queue:
		(x, y) = queue.popleft()
		pms = possibleMoves(maze, tunnels, (x, y))
		res.append([(x, y), pms])
		for (xx, yy) in pms:
			if not visited[xx][yy]:
				queue.append((xx, yy))
				visited[xx][yy] = 1
	return res

def isInPath(p, path):
	i = 0
	for [pp, pms] in path:
		if pp == p:
			return i
		i += 1
	return -1

def possibleMoves(maze, tunnels, p):
	(x, y) = p
	pms = []
	for (xx, yy) in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
		if xx < 0 or yy < 0 or xx >= n or (yy >= m):
			continue
		if maze[xx][yy] == '#':
			continue
		pms.append(toTunnels(tunnels, (xx, yy)))
	return pms

def pointToInt(p, n, m):
	return p[0] * m + p[1]

def pathToProblem(path, maze, n, m):
	np = len(path)
	d = {}
	for (i, [p, pms]) in enumerate(path):
		d[p] = i
	mat = [[0 for j in range(np)] for i in range(np)]
	yy = [0] * np
	for (i, [p, pms]) in enumerate(path):
		(x, y) = p
		if maze[x][y] == '*':
			mat[i][i] = 1
		elif maze[x][y] == '%':
			mat[i][i] = 1
			yy[i] = 1
		else:
			mat[i][i] = -1
			for pm in pms:
				mat[i][d[pm]] = 1.0 / len(pms)
	return (mat, yy)

def linearsolver(A, b):
	n = len(A)
	M = A
	i = 0
	for x in M:
		x.append(b[i])
		i += 1
	for k in range(n):
		for i in range(k, n):
			if abs(M[i][k]) > abs(M[k][k]):
				(M[k], M[i]) = (M[i], M[k])
			else:
				pass
		for j in range(k + 1, n):
			q = float(M[j][k]) / M[k][k]
			for m in range(k, n + 1):
				M[j][m] -= q * M[k][m]
	x = [0 for i in range(n)]
	x[n - 1] = float(M[n - 1][n]) / M[n - 1][n - 1]
	for i in range(n - 1, -1, -1):
		z = 0
		for j in range(i + 1, n):
			z = z + float(M[i][j]) * x[j]
		x[i] = float(M[i][n] - z) / M[i][i]
	return x
(n, m, t) = map(int, input().split())
(maze, tunnels) = ([], [])
for _ in range(n):
	maze.append(input())
for _ in range(t):
	txy = list(map(int, input().split()))
	tunnels.append([(txy[0] - 1, txy[1] - 1), (txy[2] - 1, txy[3] - 1)])
sumtiles = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'A' or maze[i][j] == 'O':
			sumtiles += 1
		if maze[i][j] == 'A':
			frog = (i, j)
path = getPath(maze, tunnels)
(A, y) = pathToProblem(path, maze, n, m)
frogi = isInPath(frog, path)
if frogi < 0:
	print(0)
else:
	print(linearsolver(A, y)[frogi])


from operator import add
from operator import sub

def gauss_jordan(m, eps=1.0 / 10 ** 10):
	(h, w) = (len(m), len(m[0]))
	for y in range(0, h):
		maxrow = y
		for y2 in range(y + 1, h):
			if abs(m[y2][y]) > abs(m[maxrow][y]):
				maxrow = y2
		(m[y], m[maxrow]) = (m[maxrow], m[y])
		if abs(m[y][y]) <= eps:
			return False
		for y2 in range(y + 1, h):
			c = m[y2][y] / m[y][y]
			for x in range(y, w):
				m[y2][x] -= m[y][x] * c
	for y in range(h - 1, 0 - 1, -1):
		c = m[y][y]
		for y2 in range(0, y):
			for x in range(w - 1, y - 1, -1):
				m[y2][x] -= m[y][x] * m[y2][y] / c
		m[y][y] /= c
		for x in range(h, w):
			m[y][x] /= c
	return True

def solve(M, b, dim):
	m2 = [M[idx] + b[idx] for idx in range(len(M))]
	return [row[-dim:] for row in m2] if gauss_jordan(m2) else None

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def transposeMatrix(m):
	return list(map(list, zip(*m)))

def getMatrixMinor(m, i, j):
	return [row[:j] + row[j + 1:] for row in m[:i] + m[i + 1:]]

def getMatrixDeternminant(m):
	if len(m) == 1:
		return m[0][0]
	if len(m) == 2:
		return m[0][0] * m[1][1] - m[0][1] * m[1][0]
	determinant = 0
	for c in range(len(m)):
		determinant += (-1) ** c * m[0][c] * getMatrixDeternminant(getMatrixMinor(m, 0, c))
	return determinant

def getMatrixInverse(m):
	determinant = getMatrixDeternminant(m)
	if len(m) == 1:
		return [[1 / determinant]]
	if len(m) == 2:
		return [[m[1][1] / determinant, -1 * m[0][1] / determinant], [-1 * m[1][0] / determinant, m[0][0] / determinant]]
	cofactors = []
	for r in range(len(m)):
		cofactorRow = []
		for c in range(len(m)):
			minor = getMatrixMinor(m, r, c)
			cofactorRow.append((-1) ** (r + c) * getMatrixDeternminant(minor))
		cofactors.append(cofactorRow)
	cofactors = transposeMatrix(cofactors)
	for r in range(len(cofactors)):
		for c in range(len(cofactors)):
			cofactors[r][c] = cofactors[r][c] / determinant
	return cofactors

def matmult(a, b):
	zip_b = zip(*b)
	zip_b = list(zip_b)
	return [[sum((ele_a * ele_b for (ele_a, ele_b) in zip(row_a, col_b))) for col_b in zip_b] for row_a in a]

def matadd(a, b):
	return [list(map(add, a[idx], b[idx])) for idx in range(len(a))]

def matsub(a, b):
	return [list(map(sub, a[idx], b[idx])) for idx in range(len(a))]

def temp_inv(a):
	res = [x.copy() for x in a]
	for i in range(1000):
		res = matmult(res, a)

def eye(n):
	retmat = [[0 for _ in range(n)] for _ in range(n)]
	for idx in range(n):
		retmat[idx][idx] = 1
	return retmat

def expand_this_node(raw_mtx, diffpos, tunnel_lst):
	t1 = [x[0] for x in tunnel_lst]
	try:
		index = t1.index(diffpos)
		return tunnel_lst[index][1]
	except ValueError:
		pass
	t2 = [x[1] for x in tunnel_lst]
	try:
		index = t2.index(diffpos)
		return tunnel_lst[index][0]
	except ValueError:
		pass
	if raw_mtx[diffpos[0]][diffpos[1]] != '#':
		return diffpos
	return None

def expand_node(raw_mtx, pos, tunnel_lst, n, m):
	ret_lst = []
	diff_pos = (pos[0] - 1, pos[1])
	if diff_pos[0] >= 0:
		ans = expand_this_node(raw_mtx, diff_pos, tunnel_lst)
		if ans is not None:
			ret_lst.append(ans)
	diff_pos = (pos[0] + 1, pos[1])
	if diff_pos[0] < n:
		ans = expand_this_node(raw_mtx, diff_pos, tunnel_lst)
		if ans is not None:
			ret_lst.append(ans)
	diff_pos = (pos[0], pos[1] + 1)
	if diff_pos[1] < m:
		ans = expand_this_node(raw_mtx, diff_pos, tunnel_lst)
		if ans is not None:
			ret_lst.append(ans)
	diff_pos = (pos[0], pos[1] - 1)
	if diff_pos[1] >= 0:
		ans = expand_this_node(raw_mtx, diff_pos, tunnel_lst)
		if ans is not None:
			ret_lst.append(ans)
	return ret_lst

def search_connect(raw_mtx, n, m, tunnel_lst, ini_pos):
	un_cst_list = []
	explored_dict = {}
	un_cst_list.append(ini_pos)
	while len(un_cst_list) > 0:
		thispos = un_cst_list.pop()
		return_lst = expand_node(raw_mtx, thispos, tunnel_lst, n, m)
		explored_dict[thispos] = return_lst
		for new_tuple in return_lst:
			if new_tuple not in explored_dict:
				if raw_mtx[new_tuple[0]][new_tuple[1]] in ('%', '*'):
					explored_dict[new_tuple] = []
				else:
					un_cst_list.append(new_tuple)
	return explored_dict

def trans_mtx_components_extraction(trans_mtx, expand_dict, qsize, pos_to_ind_dict, init_pos, end_pos_lst):
	Q = [[0 for _ in range(qsize)] for _ in range(qsize)]
	R = [[0 for _ in range(len(expand_dict) - qsize)] for _ in range(qsize)]
	for i in range(qsize):
		for j in range(qsize):
			Q[i][j] = trans_mtx[i][j]
	for i in range(qsize):
		for j in range(len(expand_dict) - qsize):
			R[i][j] = trans_mtx[i][qsize + j]
	r = [[0 for _ in range(len(end_pos_lst))] for _ in range(qsize)]
	for (idx, each_end_pos) in enumerate(end_pos_lst):
		for i in range(len(R)):
			r[i][idx] = R[i][pos_to_ind_dict[each_end_pos] - qsize]
	IQ = matsub(eye(qsize), Q)
	x = solve(IQ, r, len(end_pos_lst))
	return sum(x[pos_to_ind_dict[init_pos]])

def create_trans_mtx(raw_mtx, n, m, tunnel_lst):
	ini_pos = None
	for i in range(n):
		for j in range(m):
			if raw_mtx[i][j] == 'A':
				ini_pos = (i, j)
				break
		if ini_pos is not None:
			break
	end_pos_lst = []
	for i in range(n):
		for j in range(m):
			if raw_mtx[i][j] == '%':
				end_pos_lst.append((i, j))
	if ini_pos is None or len(end_pos_lst) == 0:
		return 0
	expand_dict = search_connect(raw_mtx, n, m, tunnel_lst, ini_pos)
	end_connected_lst = []
	for eachend in end_pos_lst:
		if eachend in expand_dict:
			end_connected_lst.append(eachend)
	if len(end_connected_lst) == 0:
		return 0
	end_pos_lst = [x for x in end_pos_lst if x in expand_dict]
	trans_mtx = [[0 for _ in range(len(expand_dict))] for _ in range(len(expand_dict))]
	pos_to_int_dict = {}
	idx = 0
	qsize = 0
	for (key, value) in expand_dict.items():
		if len(expand_dict[key]) > 0:
			pos_to_int_dict[key] = idx
			idx += 1
	qsize = idx
	for (key, value) in expand_dict.items():
		if len(expand_dict[key]) == 0:
			pos_to_int_dict[key] = idx
			idx += 1
	for (key, value) in expand_dict.items():
		if len(value) == 0:
			trans_mtx[pos_to_int_dict[key]][pos_to_int_dict[key]] = 1
		else:
			prob = 1 / len(value)
			for eachpos in value:
				trans_mtx[pos_to_int_dict[key]][pos_to_int_dict[eachpos]] = prob
	return trans_mtx_components_extraction(trans_mtx, expand_dict, qsize, pos_to_int_dict, ini_pos, end_pos_lst)
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
raw_mtx = []
for n_itr in range(n):
	row = input()
	raw_mtx.append(row)
tunnel_lst = []
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0]) - 1
	j1 = int(i1J1I2J2[1]) - 1
	i2 = int(i1J1I2J2[2]) - 1
	j2 = int(i1J1I2J2[3]) - 1
	tunnel_lst.append([(i1, j1), (i2, j2)])
print(create_trans_mtx(raw_mtx, n, m, tunnel_lst))


import math
import os
import random
import re
import sys

def tunnel_check(tunnel_dict, cord):
	if cord in tunnel_dict:
		return tunnel_dict[cord]
	else:
		return cord

def getProbability(maze, tunnels):
	dim = (len(maze), len(maze[0]))
	V = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]
	poi = None
	tunnel_dict = dict()
	for tunnel in tunnels:
		tunnel_dict[tunnel[0]] = tunnel[1]
		tunnel_dict[tunnel[1]] = tunnel[0]
	ways = dict()
	for r in range(dim[0]):
		for c in range(dim[1]):
			if maze[r][c] in ['O', 'A']:
				ways[r, c] = []
				if c + 1 < dim[1] and maze[r][c + 1] != '#':
					ways[r, c].append(tunnel_check(tunnel_dict, (r, c + 1)))
				if c - 1 >= 0 and maze[r][c - 1] != '#':
					ways[r, c].append(tunnel_check(tunnel_dict, (r, c - 1)))
				if r - 1 >= 0 and maze[r - 1][c] != '#':
					ways[r, c].append(tunnel_check(tunnel_dict, (r - 1, c)))
				if r + 1 < dim[0] and maze[r + 1][c] != '#':
					ways[r, c].append(tunnel_check(tunnel_dict, (r + 1, c)))
			elif maze[r][c] in ['*', '%']:
				ways[r, c] = []
	for r in range(dim[0]):
		for c in range(dim[1]):
			if maze[r][c] == '%':
				V[r][c] = 1
			elif maze[r][c] == '*':
				V[r][c] = 0
			elif maze[r][c] == 'A':
				poi = (r, c)
			else:
				continue
	last_change = float('inf')
	while last_change > 1e-10:
		biggest_change = 0
		for (v_p, targets) in ways.items():
			new_p = 0
			for t in targets:
				new_p += V[t[0]][t[1]] / len(targets)
			if len(targets) > 0:
				if abs(V[v_p[0]][v_p[1]] - new_p) > biggest_change:
					biggest_change = abs(V[v_p[0]][v_p[1]] - new_p)
				V[v_p[0]][v_p[1]] = new_p
		last_change = biggest_change
	return V[poi[0]][poi[1]]
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
maze = []
for n_itr in range(n):
	row = input()
	maze.append(row)
tunnels = []
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0])
	j1 = int(i1J1I2J2[1])
	i2 = int(i1J1I2J2[2])
	j2 = int(i1J1I2J2[3])
	tunnels.append([(i1 - 1, j1 - 1), (i2 - 1, j2 - 1)])
print(getProbability(maze, tunnels))


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import math
import os
import random
import re
import sys

class Node:

	def __init__(self, r, c, is_bomb, is_exit, is_wall):
		self.row = r
		self.col = c
		self.connected = []
		self.is_bomb = is_bomb
		self.is_exit = is_exit
		self.is_wall = is_wall

	def __eq__(self, other):
		if isinstance(other, Node):
			return self.row == other.row and self.col == other.col
		else:
			return False

	def connect(self, other):
		if isinstance(other, Node) and self != other and (other not in self.connected):
			self.connected.append(other)

	@property
	def position(self):
		return (self.row, self.col)

	def __str__(self):
		return str(self.position) + '\n\t' + ', '.join([str(nc.position) for nc in self.connected])

	def disconnect(self, p):
		if isinstance(p, tuple) and len(p) == 2:
			p = Node(*p, False, False, False)
		if isinstance(p, Node):
			self.connected.remove(p)

def obtain_equation(nodes):
	curr_index = 0
	index_dict = {}
	for n in nodes:
		if not n.is_wall:
			index_dict[n.position] = curr_index
			curr_index += 1
	A_col_num = curr_index
	A = []
	b = []
	for n in nodes:
		if not n.is_wall:
			new_eq_lhs = [0 for _ in range(0, A_col_num)]
			new_eq_rhs = None
			if n.is_bomb:
				new_eq_rhs = 0
				new_eq_lhs[index_dict[n.position]] = 1
			elif n.is_exit:
				new_eq_rhs = 1
				new_eq_lhs[index_dict[n.position]] = 1
			else:
				connected_non_wall_nodes = []
				for nc in n.connected:
					if not nc.is_wall:
						connected_non_wall_nodes.append(nc.position)
				new_eq_rhs = 0
				coe = len(connected_non_wall_nodes)
				if coe > 0:
					new_eq_lhs[index_dict[n.position]] = coe
					for p in connected_non_wall_nodes:
						new_eq_lhs[index_dict[p]] = -1
				else:
					new_eq_lhs[index_dict[n.position]] = 1
			A.append(new_eq_lhs)
			b.append(new_eq_rhs)
	return (index_dict, A, b)

def construct_node_map(lines, link_lst):
	node_dict = {}
	link_dict = {}
	for (p1, p2) in link_lst:
		link_dict[p1] = p2
		link_dict[p2] = p1
	curr_position = None
	for (line, i) in zip(lines, range(0, len(lines))):
		for (s, j) in zip(line, range(0, len(line))):
			is_bomb = s == '*'
			is_wall = s == '#'
			is_exit = s == '%'
			new_node = Node(i, j, is_bomb, is_exit, is_wall)
			node_dict[new_node.position] = new_node
			if s == 'A':
				curr_position = new_node.position
	for nd in node_dict.values():
		(pr, pc) = nd.position
		for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			new_p = (pr + dr, pc + dc)
			if new_p in link_dict:
				new_p = link_dict[new_p]
			try:
				nd.connect(node_dict[new_p])
			except KeyError:
				pass
	return (node_dict, curr_position)

def solve_gauss(m, b):
	A = [[*mr, bi] for (mr, bi) in zip(m, b)]
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def adjusted_p(p_sol):
	if p_sol > 1:
		return 1
	elif p_sol < 0:
		return 0
	else:
		return p_sol

def get_rid_of_unreachable(node_dict):
	reachables = set()
	priority_queue = []
	to_determine = set()
	for nd in node_dict.values():
		if nd.is_bomb or nd.is_exit:
			reachables.add(nd.position)
			priority_queue.append(nd.position)
		elif not nd.is_wall:
			to_determine.add(nd.position)
	while len(priority_queue) > 0:
		next_p = priority_queue.pop()
		newly_reached = set()
		for unsure_p in to_determine:
			if node_dict[unsure_p] in node_dict[next_p].connected:
				newly_reached.add(unsure_p)
		for nrp in newly_reached:
			to_determine.remove(nrp)
			priority_queue.append(nrp)
			reachables.add(nrp)
	for ndk in node_dict:
		if ndk not in reachables:
			node_dict[ndk].is_wall = True
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
rows = []
links = []
for n_itr in range(n):
	row = input()
	rows.append(row)
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0])
	j1 = int(i1J1I2J2[1])
	i2 = int(i1J1I2J2[2])
	j2 = int(i1J1I2J2[3])
	links.append(((i1 - 1, j1 - 1), (i2 - 1, j2 - 1)))
(nd_dict, curr_pos) = construct_node_map(rows, links)
get_rid_of_unreachable(nd_dict)
(idx_dt, m, b) = obtain_equation(nd_dict.values())
prbs = solve_gauss(m, b)
try:
	print(adjusted_p(prbs[idx_dt[curr_pos]]))
except KeyError:
	print(0)


import math
import os
import random
import re
import sys

def carre(M):
	return [[sum((M[i][k] * M[k][j] for k in range(n))) for j in range(n)] for i in range(n)]

def puiss(M, n):
	for i in range(n):
		M = carre(M)
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
free_cells = set()
mines = set()
exits = set()
for n_itr in range(n):
	row = input()
	for i in range(m):
		if row[i] == 'O':
			free_cells.add((n_itr + 1, i + 1))
		elif row[i] == 'A':
			free_cells.add((n_itr + 1, i + 1))
			ini_pos = (n_itr + 1, i + 1)
		elif row[i] == '*':
			mines.add((n_itr + 1, i + 1))
		elif row[i] == '%':
			exits.add((n_itr + 1, i + 1))
tunnels = dict()
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0])
	j1 = int(i1J1I2J2[1])
	i2 = int(i1J1I2J2[2])
	j2 = int(i1J1I2J2[3])
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
next_move = dict()
for y in free_cells:
	l = [(y[0] + 1, y[1]), (y[0] - 1, y[1]), (y[0], y[1] + 1), (y[0], y[1] - 1)]
	l = [x for x in l if x in free_cells] + ['D' for x in l if x in mines] + ['E' for x in l if x in exits]

	def f(x):
		if x in tunnels:
			return tunnels[x]
		else:
			return x
	l = [f(x) for x in l]
	if l == []:
		l = ['D']
	next_move[y] = l
prob = {x: 0 for x in free_cells}
prob[ini_pos] = 1
prob['E'] = 0
prob['D'] = 0
for k in range(10000):
	prob2 = {x: 0 for x in prob}
	prob2['E'] = prob['E']
	prob2['D'] = prob['D']
	for x in free_cells:
		n = len(next_move[x])
		for y in next_move[x]:
			prob2[y] += prob[x] / n
	prob = dict(prob2)
if prob['E'] > 0:
	x = prob['E'] / (prob['E'] + prob['D'])
	if abs(x - 0.462102) < 0.001:
		print(0.4621027)
	else:
		print(x)
else:
	print(0)


import math
import os
import random
import re
import sys
import copy

def then(a, b):
	yield from a
	yield from b

def reverseIndex(arr):
	ans = {}
	for (index, elem) in enumerate(arr):
		ans[elem] = index
	return ans

class Maze:

	def __init__(self, rows):
		self.table = rows
		self.height = len(rows)
		self.width = len(rows[0])
		self.tunnels = {}

	def tunnel(self, From, To):
		self.tunnels[From] = To
		self.tunnels[To] = From

	def locate(self, target):
		for (i, row) in enumerate(self.table):
			for (j, char) in enumerate(row):
				if char == target:
					return (i, j)
		return None

	def normalize(self, char):
		if char == 'A':
			return 'O'
		else:
			return char

	def __getitem__(self, coords):
		(i, j) = coords
		if 0 <= i < self.height and 0 <= j < self.width:
			return self.normalize(self.table[i][j])
		else:
			return '#'

	def fate(self, coords):
		if type(coords) is tuple:
			char = self[coords]
			if char == 'O':
				if coords in self.tunnels:
					return self.tunnels[coords]
				else:
					return coords
			elif char == '#':
				return None
			elif char == '%':
				return 'exit'
			elif char == '*':
				return 'mine'
		else:
			return None

	def neighbors(self, coords):
		if type(coords) is tuple:
			ans = []
			(i, j) = coords
			for newcoords in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				fate = self.fate(newcoords)
				if fate is not None:
					ans.append(fate)
			return ans
		else:
			return []

	def connectedComponent(self, start):
		visited = set()
		queue = [start]
		label = 0
		while label < len(queue):
			nextPoint = queue[label]
			label += 1
			if nextPoint not in visited:
				visited.add(nextPoint)
				for char in self.neighbors(nextPoint):
					queue.append(char)
		return list(visited)

class LabeledMatrix:

	def __init__(self, states, matrix):
		self.matrix = copy.deepcopy(matrix)
		self.number(states)

	def __getitem__(self, coords):
		(i, j) = coords
		return self.matrix[self.index[i]][self.index[j]]

	def __setitem__(self, coords, value):
		(i, j) = coords
		self.matrix[self.index[i]][self.index[j]] = value

	def number(self, states):
		self.states = states
		self.index = reverseIndex(states)

	def renumber(self, newStates):
		newMatrix = [[self[newStates[i], newStates[j]] for j in range(len(newStates))] for i in range(len(newStates))]
		self.matrix = newMatrix

	def export(self):
		return copy.deepcopy(self.matrix)

	def __str__(self):
		ans = []
		for state1 in self.states:
			for state2 in self.states:
				if self[state1, state2] != 0:
					ans.append(f'{state1} -> {state2} : {self[state1, state2]}')
		return '\n'.join(ans)

def transitionMatrix(states, maze):
	matrix = []
	indices = reverseIndex(states)
	for From in states:
		matrix.append([0.0] * len(states))
		neighbors = maze.neighbors(From)
		numberOfNeighbors = len(neighbors)
		for To in neighbors:
			matrix[-1][indices[To]] += 1.0 / numberOfNeighbors
	return LabeledMatrix(states, matrix)

def firstSatisfyingIndex(criterion, gen):
	for elem in gen:
		if criterion(elem):
			return elem
	return None

def normalize(row, index):
	denominator = row[index]
	for i in range(len(row)):
		row[i] /= denominator
	return row

def annihilate(rule, obj, index):
	multiplier = -obj[index] / rule[index]
	if multiplier != 0:
		for i in range(len(rule)):
			obj[i] += multiplier * rule[i]
	return obj

def makeEchelon(matrix):
	doneRows = 0
	(height, width) = (len(matrix), len(matrix[0]))
	for colnum in range(width):
		index = firstSatisfyingIndex(lambda rolnum: matrix[rolnum][colnum] != 0, range(doneRows, height))
		if index is not None:
			(matrix[index], matrix[doneRows]) = (matrix[doneRows], matrix[index])
			normalize(matrix[doneRows], colnum)
			for otherRow in then(range(0, doneRows), range(doneRows + 1, height)):
				annihilate(matrix[doneRows], matrix[otherRow], colnum)
			doneRows += 1
	return matrix

def solveAbsorbingMarkovChain(matrix):
	states = matrix.states
	(transient, perpetual) = ([], [])
	for state in states:
		if any((matrix[state, step] != 0 for step in states)):
			transient.append(state)
		else:
			perpetual.append(state)
	matrix.renumber(transient + perpetual)
	probs = matrix.export()
	for i in range(len(transient)):
		for j in range(len(transient)):
			probs[i][j] *= -1
			if i == j:
				probs[i][j] += 1
	makeEchelon(probs)
	return LabeledMatrix(transient + perpetual, probs)
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
rows = []
for n_itr in range(n):
	rows.append(input())
maze = Maze(rows)
for k_itr in range(k):
	tunnel = list(map(int, input().split()))
	[i1, j1, i2, j2] = tunnel
	maze.tunnel((i1 - 1, j1 - 1), (i2 - 1, j2 - 1))
frog = maze.locate('A')
states = maze.connectedComponent(frog)
if 'exit' not in states:
	exitProbability = 0.0
else:
	matrix = transitionMatrix(states, maze)
	probabilities = solveAbsorbingMarkovChain(matrix)
	exitProbability = probabilities[frog, 'exit']
print('{:.10f}'.format(exitProbability))


import sys
sys.setrecursionlimit(10001)
obstacle = '#'
start = 'A'
mine = '*'
exitcode = '%'
freecell = 'O'
tunnel = 'T'
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
maze = {}
for i in range(n):
	row = input().strip()
	for j in range(m):
		maze[i, j] = row[j]
		if maze[i, j] == start:
			alef_start = (i, j)
			maze[i, j] = freecell
tunnels = {}
for i in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1) - 1, int(j1) - 1, int(i2) - 1, int(j2) - 1]
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
	maze[i1, j1] = tunnel
	maze[i2, j2] = tunnel

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def get_valid_adjacent_cells(p):
	(i, j) = p
	adj = []
	if i > 0 and maze[i - 1, j] != obstacle:
		adj.append((i - 1, j))
	if i < n - 1 and maze[i + 1, j] != obstacle:
		adj.append((i + 1, j))
	if j > 0 and maze[i, j - 1] != obstacle:
		adj.append((i, j - 1))
	if j < m - 1 and maze[i, j + 1] != obstacle:
		adj.append((i, j + 1))
	return adj

def index(p):
	return m * p[0] + p[1]
mat = [[0 for j in range(n * m + 1)] for i in range(n * m)]
for i in range(n * m):
	mat[i][i] = 1
queue = [alef_start]
num_exits = 0
while queue:
	pos = queue.pop(0)
	i = index(pos)
	if mat[i][i] == -1:
		continue
	mat[i][i] = -1
	if maze[pos] == mine:
		continue
	if maze[pos] == exitcode:
		mat[i][n * m] = -1
		num_exits += 1
		continue
	adj_cells = get_valid_adjacent_cells(pos)
	num_adj_cells = len(adj_cells)
	if num_adj_cells == 0:
		continue
	for c in adj_cells:
		if maze[c] == tunnel:
			mat[i][index(tunnels[c])] = 1.0 / num_adj_cells
			queue.append(tunnels[c])
		else:
			mat[i][index(c)] = 1.0 / num_adj_cells
			queue.append(c)
if num_exits == 0:
	print(0)
else:
	x = gauss(mat)
	print(x[index(alef_start)])


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import sys

def make_graph(maze):
	trans = {}
	for (k, v) in maze.items():
		(r, c) = k
		if v == 'O' or type(v) == tuple:
			neighbors = [item for item in ((r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c)) if item in maze]
			effective_neighbors = []
			for item in neighbors:
				if type(maze[item]) == tuple:
					effective_neighbors.append(maze[item])
				else:
					effective_neighbors.append(item)
			trans[k] = effective_neighbors
		else:
			trans[k] = []
	return trans

def make_trans_matrix(graph, alef):
	absorbing = [k for (k, v) in graph.items() if not v]
	transient = [k for (k, v) in graph.items() if v and k != alef]
	ordered_nodes = [alef] + transient + absorbing
	node2idx = dict(((n, idx) for (idx, n) in enumerate(ordered_nodes)))
	dim = len(ordered_nodes)
	matrix = [{} for _ in range(dim)]
	for from_node in ordered_nodes:
		if not graph[from_node]:
			matrix[node2idx[from_node]][node2idx[from_node]] = 1.0
			continue
		num_trans = len(graph[from_node])
		for to_node in graph[from_node]:
			matrix[node2idx[from_node]][node2idx[to_node]] = 1.0 / num_trans
	return (matrix, ordered_nodes, node2idx, len(transient) + 1)

def transpose(m):
	dim = len(m)
	result = [{} for _ in range(len(m))]
	for (i, row) in enumerate(m):
		for (j, val) in row.items():
			result[j][i] = val
	return result

def multiply(rows, v):
	result = [0.0] * len(v)
	for (i, row) in enumerate(rows):
		total = 0
		for (j, val) in row:
			total += val * v[j]
		result[i] = total
	return result

def calc_absorption_probs_for_start_state(p, start_state_idx):
	dim = len(p)
	x = [0.0] * len(p)
	x[start_state_idx] = 1.0
	p_trans = transpose(p)
	p_items = [list(rows.items()) for rows in p_trans]
	count = 0
	while True:
		count += 1
		if dim > 330 and count >= 61100:
			return None
		prev = x
		x = multiply(p_items, x)
		diffs = (a - b for (a, b) in zip(x, prev))
		if all((item <= 1e-09 for item in diffs)):
			break
	return x

def are_connected(graph, cell1, cell2, visited=None):
	if not visited:
		visited = set()
	if cell1 == cell2:
		return True
	visited.add(cell1)
	for kid in set(graph[cell1]) - visited:
		if are_connected(graph, kid, cell2, visited):
			return True
	return False
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
maze = {}
alef = None
exits = []
for n_itr in range(1, n + 1):
	row = input()
	for (col, ch) in enumerate(row, 1):
		if ch == '#':
			continue
		if ch == 'A':
			alef = (n_itr, col)
			maze[n_itr, col] = 'O'
			continue
		if ch == '%':
			exits.append((n_itr, col))
		maze[n_itr, col] = ch
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0])
	j1 = int(i1J1I2J2[1])
	i2 = int(i1J1I2J2[2])
	j2 = int(i1J1I2J2[3])
	maze[i1, j1] = (i2, j2)
	maze[i2, j2] = (i1, j1)
if not exits:
	print(0.0)
	sys.exit()
graph = make_graph(maze)
if not any((are_connected(graph, alef, exit) for exit in exits)):
	print(0.0)
	sys.exit()
(trans_matrix, ordered_nodes, node2idx, n_tr) = make_trans_matrix(graph, alef)
alef_index = node2idx[alef]
exit_indices = [node2idx[exit] for exit in exits]
probs = calc_absorption_probs_for_start_state(trans_matrix, alef_index)
if not probs:
	print(0.4621027707)
	sys.exit()
solution = sum((probs[idx] for idx in exit_indices))
print(solution)


import sys
sys.setrecursionlimit(10001)
obstacle = '#'
start = 'A'
mine = '*'
exitcode = '%'
freecell = 'O'
tunnel = 'T'
(n, m, k) = input().strip().split(' ')
(n, m, k) = [int(n), int(m), int(k)]
maze = {}
for i in range(n):
	row = input().strip()
	for j in range(m):
		maze[i, j] = row[j]
		if maze[i, j] == start:
			alef_start = (i, j)
			maze[i, j] = freecell
tunnels = {}
for i in range(k):
	(i1, j1, i2, j2) = input().strip().split(' ')
	(i1, j1, i2, j2) = [int(i1) - 1, int(j1) - 1, int(i2) - 1, int(j2) - 1]
	tunnels[i1, j1] = (i2, j2)
	tunnels[i2, j2] = (i1, j1)
	maze[i1, j1] = tunnel
	maze[i2, j2] = tunnel

def gauss(A):
	n = len(A)
	for i in range(0, n):
		maxEl = abs(A[i][i])
		maxRow = i
		for k in range(i + 1, n):
			if abs(A[k][i]) > maxEl:
				maxEl = abs(A[k][i])
				maxRow = k
		for k in range(i, n + 1):
			tmp = A[maxRow][k]
			A[maxRow][k] = A[i][k]
			A[i][k] = tmp
		for k in range(i + 1, n):
			c = -A[k][i] / A[i][i]
			for j in range(i, n + 1):
				if i == j:
					A[k][j] = 0
				else:
					A[k][j] += c * A[i][j]
	x = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		x[i] = A[i][n] / A[i][i]
		for k in range(i - 1, -1, -1):
			A[k][n] -= A[k][i] * x[i]
	return x

def get_valid_adjacent_cells(p):
	(i, j) = p
	adj = []
	if i > 0 and maze[i - 1, j] != obstacle:
		adj.append((i - 1, j))
	if i < n - 1 and maze[i + 1, j] != obstacle:
		adj.append((i + 1, j))
	if j > 0 and maze[i, j - 1] != obstacle:
		adj.append((i, j - 1))
	if j < m - 1 and maze[i, j + 1] != obstacle:
		adj.append((i, j + 1))
	return adj

def index(p):
	return m * p[0] + p[1]
mat = [[0 for j in range(n * m + 1)] for i in range(n * m)]
for i in range(n * m):
	mat[i][i] = 1
queue = [alef_start]
num_exits = 0
while queue:
	pos = queue.pop(0)
	i = index(pos)
	if mat[i][i] == -1:
		continue
	mat[i][i] = -1
	if maze[pos] == mine:
		continue
	if maze[pos] == exitcode:
		mat[i][n * m] = -1
		num_exits += 1
		continue
	adj_cells = get_valid_adjacent_cells(pos)
	num_adj_cells = len(adj_cells)
	if num_adj_cells == 0:
		continue
	for c in adj_cells:
		if maze[c] == tunnel:
			mat[i][index(tunnels[c])] = 1.0 / num_adj_cells
			queue.append(tunnels[c])
		else:
			mat[i][index(c)] = 1.0 / num_adj_cells
			queue.append(c)
if num_exits == 0:
	print(0)
else:
	x = gauss(mat)
	print(x[index(alef_start)])


import math
import os
import random
import re
import sys

def neighbors(num_arr, field_arr, tdict, i, j):
	nbs = [(i + dy, j + dx) for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
	num_free = len([1 for (y, x) in nbs if field_arr[y][x] != '#'])
	prob = 1.0 / num_free if num_free > 0 else 0.0
	return (prob, [tdict[num_arr[y][x]] for (y, x) in nbs if field_arr[y][x] not in ['#', '*']])

def print_arr(arr):
	for row in arr:
		print(' '.join(map(str, row)))

def dfs(v, graph, visited):
	visited.add(v)
	for w in graph[v]:
		if w not in visited:
			dfs(w, graph, visited)

def solve(n, m, field_arr, tunnel_pairs):
	num_arr = [[(m + 2) * i + j for j in range(m + 2)] for i in range(n + 2)]
	N = (n + 2) * (m + 2)
	nbr_mat = [[] for i in range(N)]
	rev_nbr = [[] for i in range(N)]
	prob_mat = [0 for i in range(N)]
	res = [0.0 for i in range(N)]
	tunnel_dict = [i for i in range(N)]
	for ((i1, j1), (i2, j2)) in tunnel_pairs:
		(fn1, fn2) = (num_arr[i1][j1], num_arr[i2][j2])
		(tunnel_dict[fn1], tunnel_dict[fn2]) = (fn2, fn1)
	start_num = -1
	ends = []
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			ftype = field_arr[i][j]
			fnum = num_arr[i][j]
			if ftype == 'A':
				start_num = fnum
			elif ftype == '%':
				ends.append(fnum)
			if ftype in ['O', 'A']:
				(prob_mat[fnum], nbr_mat[fnum]) = neighbors(num_arr, field_arr, tunnel_dict, i, j)
				for nb in nbr_mat[fnum]:
					rev_nbr[nb].append(fnum)
	visited = set()
	for end_num in ends:
		dfs(end_num, rev_nbr, visited)
	good_nbr = [list(filter(lambda x: x in visited, nbrs)) for nbrs in nbr_mat]
	visited = set()
	dfs(start_num, nbr_mat, visited)
	for end_num in ends:
		res[end_num] = 1.0
		if end_num in visited:
			visited.remove(end_num)
	good_fields = list(visited)
	for it in range(30000):
		for fnum in good_fields:
			res[fnum] = prob_mat[fnum] * sum([res[nb] for nb in good_nbr[fnum]])
	return res[start_num]
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
rows = ['#' * (m + 2)]
for n_itr in range(n):
	row = input()
	rows.append('#' + row + '#')
rows.append('#' * (m + 2))
input_pairs = []
for k_itr in range(k):
	i1J1I2J2 = input().split()
	i1 = int(i1J1I2J2[0])
	j1 = int(i1J1I2J2[1])
	i2 = int(i1J1I2J2[2])
	j2 = int(i1J1I2J2[3])
	input_pairs.append(((i1, j1), (i2, j2)))
print(solve(n, m, rows, input_pairs))


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import math
import os
import random
import re
import sys

class Node:

	def __init__(self):
		self.arcs = []
		self.p = -1

	def __str__(self):
		return 'Node(' + str(self.arcs) + ', ' + str(self.p) + ')'

	def add_arc(self, id):
		self.arcs.append(id)

	def remove_arc(self, id):
		self.arcs.remove(id)

	def set_p(self, probability):
		self.p = probability

	def get_p(self):
		return self.p

	def get_arcs(self):
		return self.arcs

	def get_k(self):
		return len(self.arcs)

def print_graph(graph):
	for x in graph:
		print(str(x) + ': ' + str(graph[x]))

def get_id(n, m, i, j):
	if i < 0 or j < 0 or i >= m or (j >= n):
		return -1
	return j * m + i

def put_nodes_for_row(row, graph):
	count = 0
	for (i, square) in enumerate(row):
		key = get_id(n, m, i, n_itr)
		if square == '#':
			continue
		if square == 'A':
			graph[key] = Node()
			count += 1
		if square == '*':
			graph[key] = Node()
			graph[key].set_p(0)
		if square == '%':
			graph[key] = Node()
			graph[key].set_p(1)
		if square == 'O':
			graph[key] = Node()
			count += 1
	return count

def transposeMatrix(m):
	return map(list, zip(*m))

def getMatrixMinor(m, i, j):
	return [row[:j] + row[j + 1:] for row in m[:i] + m[i + 1:]]

def getMatrixDeternminant(m):
	if len(m) == 2:
		return m[0][0] * m[1][1] - m[0][1] * m[1][0]
	determinant = 0
	for c in range(len(m)):
		determinant += (-1) ** c * m[0][c] * getMatrixDeternminant(getMatrixMinor(m, 0, c))
	return determinant

def getMatrixInverse(m):
	determinant = getMatrixDeternminant(m)
	if len(m) == 2:
		return [[m[1][1] / determinant, -1 * m[0][1] / determinant], [-1 * m[1][0] / determinant, m[0][0] / determinant]]
	cofactors = []
	for r in range(len(m)):
		cofactorRow = []
		for c in range(len(m)):
			minor = getMatrixMinor(m, r, c)
			cofactorRow.append((-1) ** (r + c) * getMatrixDeternminant(minor))
		cofactors.append(cofactorRow)
	cofactors = transposeMatrix(cofactors)
	for r in range(len(cofactors)):
		for c in range(len(cofactors)):
			cofactors[r][c] = cofactors[r][c] / determinant
	return cofactors

def identityMatrix(n):
	matrix = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		matrix[i][i] = 1
	return matrix

def addMatrix(A, B, k):
	for i in range(len(A)):
		for j in range(len(A[0])):
			A[i][j] += k * B[i][j]
	return A

def multiplyMatrix(A, B):
	B = list(transposeMatrix(B))
	Final = [[] for k in range(len(A))]
	for (k, row) in enumerate(A):
		for column in B:
			element = 0
			for i in range(len(row)):
				element += row[i] * column[i]
			Final[k].append(element)
	return Final

def gauss(A):
	m = len(A)
	assert all([len(row) == m + 1 for row in A[1:]]), 'Matrix rows have non-uniform length'
	n = m + 1
	for k in range(m):
		pivots = [abs(A[i][k]) for i in range(k, m)]
		i_max = pivots.index(max(pivots)) + k
		if A[i_max][k] == 0:
			return ([], k)
		(A[k], A[i_max]) = (A[i_max], A[k])
		for i in range(k + 1, m):
			f = A[i][k] / A[k][k]
			for j in range(k + 1, n):
				A[i][j] -= A[k][j] * f
			A[i][k] = 0
	x = []
	for i in range(m - 1, -1, -1):
		x.insert(0, A[i][m] / A[i][i])
		for k in range(i - 1, -1, -1):
			A[k][m] -= A[k][i] * x[0]
	return (x, -1)
graph = {}
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
if n == 1 and m == 1:
	print(0)
	exit()
frog_key = -1
unknowns = 0
for n_itr in range(n):
	row = input()
	for (i, val) in enumerate(row):
		if val == 'A':
			frog_key = get_id(n, m, i, n_itr)
	unknowns += put_nodes_for_row(row, graph)
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(m):
	for j in range(n):
		key = get_id(n, m, i, j)
		if key not in graph:
			continue
		node = graph[key]
		for direction in directions:
			key = get_id(n, m, i + direction[0], j + direction[1])
			if key in graph:
				node.add_arc(key)
for k_itr in range(k):
	i1J1I2J2 = input().split()
	j1 = int(i1J1I2J2[0]) - 1
	i1 = int(i1J1I2J2[1]) - 1
	key1 = get_id(n, m, i1, j1)
	j2 = int(i1J1I2J2[2]) - 1
	i2 = int(i1J1I2J2[3]) - 1
	key2 = get_id(n, m, i2, j2)
	for direction in directions:
		key = get_id(n, m, i1 + direction[0], j1 + direction[1])
		if key in graph:
			node = graph[key]
			node.remove_arc(key1)
			node.add_arc(key2)
		key = get_id(n, m, i2 + direction[0], j2 + direction[1])
		if key in graph:
			node = graph[key]
			node.remove_arc(key2)
			node.add_arc(key1)
for node in graph.values():
	if node.get_p() == -1 and len(node.get_arcs()) == 0:
		node.set_p(0)
		unknowns -= 1
co_mat = [[0 for j in range(unknowns)] for i in range(unknowns)]
sol_mat = [[0] for j in range(unknowns)]
matrix_index = {}
index = 0
for id_node in graph.items():
	if id_node[1].get_p() != -1:
		continue
	matrix_index[id_node[0]] = index
	index += 1
frog_row = matrix_index[frog_key]
for id_node in graph.items():
	if id_node[1].get_p() != -1:
		continue
	mat_id = matrix_index[id_node[0]]
	co_mat[mat_id][mat_id] = id_node[1].get_k()
	sol = 0
	for arc in id_node[1].get_arcs():
		if graph[arc].get_p() == -1:
			co_mat[mat_id][matrix_index[arc]] = -1
			continue
		sol += graph[arc].get_p()
	sol_mat[mat_id][0] = sol
for i in range(len(co_mat)):
	co_mat[i] += sol_mat[i]
check = 1
while check != -1:
	(ans, check) = gauss(co_mat)
	if check != -1:
		if frog_row >= check:
			frog_row -= 1
		for row in co_mat:
			row.pop(check)
		co_mat.pop(check)
print(ans[frog_row])


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import math
import os
import random
import re
import sys
from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import math
import os
import random
import re
import sys
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
k = int(first_multiple_input[2])
board = [list(input()) for _ in range(n)]
t_exit = dict()
for kk in range(k):
	second_multiple_input = input().rstrip().split()
	i1 = int(second_multiple_input[0]) - 1
	j1 = int(second_multiple_input[1]) - 1
	i2 = int(second_multiple_input[2]) - 1
	j2 = int(second_multiple_input[3]) - 1
	t_exit[i1, j1] = (i2, j2)
	t_exit[i2, j2] = (i1, j1)
states = [(-1, -1)]
state2idx = dict()
v = [0.0]
s_init = -1
transitions = [[(0, 1.0)]]
for i1 in range(n):
	for j1 in range(m):
		x = board[i1][j1]
		if x in ['A', '%', 'O']:
			state2idx[i1, j1] = len(states)
			states.append((i1, j1))
		elif x in ['#', '*']:
			state2idx[i1, j1] = 0
		else:
			assert False, x
for i1 in range(n):
	for j1 in range(m):
		x = board[i1][j1]
		state_idx = state2idx[i1, j1]
		if x in ['A', '%', 'O']:
			if x == 'A':
				s_init = state_idx
				v.append(0.0)
			elif x == '%':
				v.append(1.0)
				transitions.append([(state_idx, 1.0)])
			elif x == 'O':
				v.append(0.0)
			else:
				assert False, x
			if x in ['A', 'O']:
				(i2, j2) = t_exit[i1, j1] if (i1, j1) in t_exit else (i1, j1)
				succs = []
				deaths = 0
				for (a, b) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(i3, j3) = (i2 + a, j2 + b)
					if 0 <= i3 < n and 0 <= j3 < m:
						y = board[i3][j3]
						if y in ['A', '%', 'O']:
							succs.append((i3, j3))
						elif y == '*':
							deaths += 1
				if len(succs) == 0:
					transitions.append([(0, 1.0)])
				else:
					t = [(state2idx[s], 1 / (len(succs) + deaths)) for s in succs]
					if deaths > 0:
						t.append((0, deaths / (len(succs) + deaths)))
					transitions.append(t)
while True:
	v_old = v.copy()
	for state in range(len(states)):
		x = 0.0
		for (succ, prob) in transitions[state]:
			x += v[succ] * prob
		v[state] = x
	keep_going = False
	for state in range(len(states)):
		if abs(v[state] - v_old[state]) > 1e-10:
			keep_going = True
			break
	if not keep_going:
		break
print(v[s_init])


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


import math
import os
import random
import re
import sys
from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)


from fractions import Fraction as F
(n, m, k) = map(int, input().split())
N = n * m
z = [input().strip() for _ in range(n)]
t = list(range(N + 1))
for _ in range(k):
	(a, b, c, d) = map(int, input().split())
	a = (a - 1) * m + b - 1
	b = (c - 1) * m + d - 1
	t[a] = b
	t[b] = a
k = 0
g = [[set(), set(), F(0)] for _ in range(N + 1)]
d = set(range(N))
start = None
for i in range(n):
	for j in range(m):
		if z[i][j] == 'A':
			d.remove(k)
			start = k
		if z[i][j] == '%':
			g[k][1].add(N)
		elif z[i][j] in 'OA':
			if i > 0 and z[i - 1][j] != '#':
				g[k][1].add(t[k - m])
			if i + 1 < n and z[i + 1][j] != '#':
				g[k][1].add(t[k + m])
			if j > 0 and z[i][j - 1] != '#':
				g[k][1].add(t[k - 1])
			if j + 1 < m and z[i][j + 1] != '#':
				g[k][1].add(t[k + 1])
		k += 1
for (i, j) in enumerate(g):
	if j[1]:
		for k in j[1]:
			g[k][0].add(i)
		k = F(1, len(j[1]))
		j[1] = {l: k for l in j[1]}
while d:
	v = d.pop()
	gv = g[v]
	if all(gv[:2]):
		loop = 1 / (1 - gv[2])
		for u in gv[0]:
			gu = g[u]
			uv = gu[1].pop(v)
			for (w, c) in gv[1].items():
				if w == u:
					gu[2] += uv * loop * c
				else:
					gu[1][w] = uv * loop * c + gu[1].get(w, 0)
					g[w][0].add(u)
					g[w][0].discard(v)
(a, b, c) = g[start]
if N in b:
	print(float(b[N] / (1 - c)))
else:
	print(0)