Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Raze is a new agent in Valorant Inc. Currently, she is training on how to use Boom Bot.

The training arena is an $N \times M$ grid where each cell has a height. We call a cell **ground cell** if its height is $1$.

The boom bot is placed on a cell in the grid. In each second, the bot can move to an adjacent cell whose height is **not greater** than the current cell. If there are multiple such cells, the bot picks a cell out of them randomly. If the bot reaches a ground cell, it blasts off immediately.

Raze has $Q$ queries to ask. She will place the bot on a cell and wants to know the expected time required for the boom bot to blast off.

Two cells are called adjacent if they share a side horizontally or vertically.

**It is guaranteed that there will be at least one ground cell and no two ground cells will be adjacent.**

First line contains an integer $T (1 \leq T \leq 10)$, denoting the number of testcases.

In each testcase, the first line contains two integers $N (1 \leq N \leq 20)$ and $M (1 \leq M \leq 20)$, denoting the number of rows and columns in the grid respectively.

Each of the next $N$ lines contains $M$ integers, where each integer $H_{ij} (1 \leq H_{ij} \leq 2)$ denotes the height of the cell $(i, j)$.

Following line contains an integer $Q (1 \leq Q \leq N \times M)$, denoting the number of queries.

Each of the next $Q$ lines contains two integers $X (1 \leq X \leq N)$ and $Y (1 \leq Y \leq M)$, denoting the cell where the bot will be placed.

**Subtask 1 (25 points):**$N = 1$**Subtask 2 (75 points):**Original constraints

For each query, you need to print the expected time required for the bot to blast off. The answer can be written in form $\frac{P}{Q}$ where $P$ and $Q$ are relatively prime integers and $Q \neq 0\mod 998244353$.

Output the value of $P \times Q^{-1}$ modulo $998244353$.

Input | Output |
---|---|

1 1 3 1 2 2 3 1 1 1 2 1 3 | 0 3 4 |

Input | Output |
---|---|

1 2 2 2 2 2 1 3 1 1 1 2 2 2 | 4 3 0 |

86% Solution Ratio

NirjhorEarliest,

MujahidFastest, 0.1s

NirjhorLightest, 786 kB

Deshi_TouristShortest, 2185B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.