P3315 [SDOI2014] The Drunkard

$\text{Alice}$ finds that when people are in a bad mood, they tend to drink heavily. Unlike the jubilant celebration after an $\text{OI}$ contestant’s victory, a drunkard often forgets the way home and wanders randomly around the streets, shouting incomprehensible words. These days, $\text{Bob}$ is in a bad mood due to exams. Every night he finds a bar in the city. After getting drunk and leaving the bar, he begins to wander randomly through the city streets until, at some moment, if he happens to meet $\text{Alice}$ who is out watching the stars at night, she will take him home. The city streets where $\text{Alice}$ and $\text{Bob}$ live can be modeled as a grid of $N$ rows and $M$ columns. Rows are numbered from $0$ to $N - 1$, and columns from $0$ to $M - 1$. There are $N \times M$ intersections in total, and each intersection is denoted by coordinates $(i, j)$. If $i < N - 1$, then $(i, j)$ and $(i + 1, j)$ are connected by an undirected edge whose length is $p_{(i,j)}$, representing the time needed to traverse this road. If $j < M - 1$, then $(i, j)$ and $(i, j + 1)$ are connected by an undirected edge whose length is $q_{(i,j)}$. Given two points $(u, v)$ and $(s, t)$, which are the locations of the bar that $\text{Bob}$ visits tonight and the place where $\text{Alice}$ watches the stars tonight, respectively. After leaving the bar, at each intersection, $\text{Bob}$ will choose uniformly at random one of the adjacent intersections and then move to it. Before reaching the next intersection, $\text{Bob}$ will not turn back mid-edge. Also, $\text{Bob}$’s future movement is not affected by the roads he has previously taken. Specifically: if $\text{Bob}$ moves from $(3, 4)$ to $(3, 5)$, he may immediately return to $(3, 4)$ after arriving at $(3, 5)$. At a four-way intersection, $\text{Bob}$ moves in each direction with probability $1/4$; at a three-way intersection (only on the boundary), with probability $1/3$ for each; at a two-way intersection (only at the four corners), with probability $1/2$ for each. $\text{Alice}$ wants to know, starting from when $\text{Bob}$ leaves the bar, how long she expects to wait until meeting $\text{Bob}$. That is, for the given points $(u, v)$ and $(s, t)$, what is the expected time for $\text{Bob}$ to go from $(u, v)$ to $(s, t)$?

The first line contains $N$, $M$. Then there are $N - 1$ lines, each containing $M$ positive integers, where the entry in row $i$ and column $j$ is $p_{(i,j)}$. Then there are $N$ lines, each containing $M - 1$ positive integers, where the entry in row $i$ and column $j$ is $q_{(i,j)}$. A single line follows with an integer $Q$, the number of queries. Then $Q$ lines follow, each containing four integers $u$, $v$, $s$, $t$.

Output $Q$ lines. For each query, print the expected time for $\text{Bob}$ to go from $(u, v)$ to $(s, t)$. You may output any number of decimal places, but your answer is considered correct only if the error rate is within $0.1\%$.

For $10\%$ of the testdata, $N \times M \le 25$. For $30\%$ of the testdata, $N \times M \le 625$. For $50\%$ of the testdata, $N \times M \le 2500$. For $100\%$ of the testdata, $1 \le N \times M \le 10^4$, $1 \le Q \le 100$, and $1 \le p_{(i,j)}, q_{(i,j)} \le 200$. Additionally, for $10\%$ of the testdata, $\min(N, M) \le 10$. Translated by ChatGPT 5