AT_gw2015_d.最短絡問題

在一个被划分成 $H$ 行 $W$ 列的房间内，每两个相邻的格子之间都有一扇门，门的开关需要一定的费用。我们称位于第 $i\ (1 \le i \le H)$ 行、第 $j\ (1 \le j \le W)$ 列的格子为格子 $(i, j)$。门的开关费用都是正整数，并具有以下特性：

• 对于所有 $i\ (2 \le i \le H),\ j\ (2 \le j \le W)$：
  • 格子 $(i-1,j-1)$ 和 $(i-1,j)$ 之间门的开关费用为 $A$。
  • 格子 $(i,j-1)$ 和 $(i,j)$ 之间门的开关费用为 $B$。
  • 格子 $(i-1,j-1)$ 和 $(i,j-1)$ 之间门的开关费用为 $C$。
  • 格子 $(i-1,j)$ 和 $(i,j)$ 之间门的开关费用为 $D$。
  • 满足 $A + D = B + C$ 且 $A + C \le B + D$。

从格子 $(si, sj)$ 移动到格子 $(ti, tj)$ 时，经过的相邻格子间门的开关费用之和的最小值称为 $dist(si, sj, ti, tj)$。另外，$dist(i, j, i, j) = 0$。

你已知 $H$ 和 $W$ 的值，但不了解门的开关费用。开始时，你可以进行恰好 $H \times W$ 次询问：

• 「$dist(si, sj, ti, tj)$ 的值是多少？」

然后，你需要回答 $Q$ 个同样形式的询问。

输入格式

首先输入三个整数 $H\ (1 \le H \le 20),\ W\ (1 \le W \le 20),\ Q\ (1 \le Q \le 100)$，表示房间的行数、列数和询问的次数。

接下来，在进行 $H \times W$ 次询问时，每次输出四个整数 $si\ (1 \le si \le H),\ sj\ (1 \le sj \le W),\ ti\ (1 \le ti \le H),\ tj\ (1 \le tj \le W)$，表示询问 $dist(si, sj, ti, tj)$。

完成 $H \times W$ 次询问后，程序接收 $Q$ 个新询问。每个询问输入四个整数 $Si\ (1 \le Si \le H),\ Sj\ (1 \le Sj \le W),\ Ti\ (1 \le Ti \le H),\ Tj\ (1 \le Tj \le W)$，询问 $dist(Si,Sj,Ti,Tj)$。

输出格式

对于每个询问，输出其对应的 $dist(Si, Sj, Ti, Tj)$ 的值。程序应在 $Q$ 个询问结束后立即终止，并确保每次输出后刷新缓冲区以防超时。

注意：程序必须正确回答所有询问并在输出后立即停止，否则结果将是不确定的。

示例输入输出

输入：

3 3 2
1 1 1 1
1 1 1 2
...（省略部分输入）
3 3 3 3
1 1 3 3
2 2 3 3

输出：

0
1
...（省略部分输出）
8
3
2

示例提供了部分输入与输出来说明程序的运作方式，实际数据可能有所不同。

本翻译由 AI 自动生成