P15503 [ICPC 2025 APC] Boarding Queue

你正在前往参加 2025 年 ICPC 亚太锦标赛的路上。不幸的是，你正经历飞行中最糟糕的部分：在登机队列中等待。 你与 $n$ 名旅客一同排队，旅客编号为 $1$ 到 $n$，按从队首到队尾的顺序排列。登机区域由 $r$ 行 $c$ 列的网格表示，行从上到下编号为 $1$ 到 $r$，列从左到右编号为 $1$ 到 $c$。每名旅客恰好占据网格中的一个不同单元格。如果两名旅客所在的单元格共享一条边，则称他们 **相邻**。对于任意 $2 \le t \le n$，保证旅客 $t$ 与旅客 $t-1$ 相邻。 例如，图 L.1 展示了旅客可能的位置。在此示例中，旅客 $1$ 与旅客 $2$ 和 $10$ 相邻，但与旅客 $11$ 不相邻。 :::align{center}  图 L.1：旅客位置示例。 ::: 在每个登机步骤中，以下事件同时发生： - 队列中最靠前的旅客，设为旅客 $t$，登上飞机并离开登机区域。 - 对于每个 $t'$（$t + 1 \le t' \le n$），旅客 $t'$ 占据该步骤之前旅客 $t' - 1$ 所在的单元格。 :::align{center}  图 L.2：分别经过 1、2 和 3 个登机步骤后旅客的位置。 ::: 例如，图 L.2 展示了从上述初始位置经过前三个登机步骤后旅客的位置。 你是旅客 $p$（即你前面有 $p - 1$ 名旅客）。你知道你的队伍教练在队列中的某个位置，但不知道具体在哪里。假设你的队伍教练等可能地是旅客 $1$ 到 $n$ 中的任意一人（除了 $p$ 自己），你想要计算在登机前的某个时刻你会与队伍教练相邻的概率。形式化地说，如果存在一个整数 $s$（$0 \le s < p$）使得在 $s$ 个登机步骤后，旅客 $p$ 与旅客 $q$ 相邻，则你会在登机前与旅客 $q$ 相邻。

输入的第一行包含四个整数 $r$、$c$、$n$ 和 $p$（$1 \le r, c \le 1000$；$2 \le n \le r \times c$；$1 \le p \le n$）。接下来的 $r$ 行，每行包含 $c$ 个整数。第 $i$ 行第 $j$ 个整数表示 $G_{i,j}$（$0 \le G_{i,j} \le n$），其中 $G_{i,j}$ 非零表示旅客 $G_{i,j}$ 初始时占据登机区域第 $i$ 行第 $j$ 列的单元格，$G_{i,j}$ 为零表示该单元格无旅客。在所有 $(i,j)$ 对中，整数 $1$ 到 $n$ 在 $G_{i,j}$ 中恰好出现一次。输入保证对于所有 $2 \le t \le n$，旅客 $t$ 与旅客 $t-1$ 相邻。

以 $x/y$ 格式输出一个分数，表示你在登机前的某个时刻与队伍教练相邻的概率。$y$ 的值必须等于 $n-1$。注意整数与 / 分隔符之间不能有空格。

**样例输入/输出 #1 的解释** 此示例对应于题目描述中给出的示例。如果你的队伍教练是旅客 $1$、$3$ 或 $11$，你将在登机前的某个时刻与他相邻。 **样例输入/输出 #2 的解释** 如果你的队伍教练是旅客 $5$ 或 $7$，你将在登机前的某个时刻与他相邻。注意输出 $1/3$ 是 **不** 被接受的。 翻译由 DeepSeek 完成