問題文
H 行 W 有一个房间被分成正方形的柱子。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 标记列中的方块 (i,j) 。方格之间有一扇门,打开和关闭门的成本是固定的。开门和关门的所有费用 大于或等于 1 的整数。全部 以下内容适用于 i (2 ≦ i ≦ H), j (2 ≦ j ≦ 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 ≦ B+D 成立。
质量 (si,sj) 卡拉增 (ti,tj) 计算上下左右重复移动到相邻方格时的开门/关门成本之和的最小值。 我们称之为 dist(si,sj,ti,tj) 。然而,当移动到相邻的格子时,打开和关闭这些格子之间的门是有成本的。另外,任何 对于 i,j ,dist(i,j,i,j) = 0 没问题。
你是 我知道H 和 W 的价值,但我不知道开关门的成本。你先
- dist(si,sj,ti,tj) 的值是多少? 只需提出
形式的问题 执行 H \times W 次。然后是类似的格式 您必须回答 Q 问题。
入出力
首先,表示网格的行数和列数以及问题的数量。 3 整数 H (1 ≦ H ≦ 20), W (1 ≦ W ≦ 20), Q (1 ≦ Q ≦ 100) 被赋予由空格分隔的标准输入。
H W Q
那么你的程序应该是 您必须询问 H \times W 次。
对于每个问题,首先, 输出4 整数 si (1 ≦ si ≦ H), sj (1 ≦ sj ≦ W), ti (1 ≦ ti ≦ H), tj (1 ≦ tj ≦ W) 以空格分隔。这是dist(si,sj,ti,tj) 的值是多少? ” 代表问题。
si sj ti tj
那么你的程序将会有 给出了值 dist(si,sj,ti,tj) 。 在任何情况下 保证不超过 dist(si,sj,ti,tj) 是 10^9 。 在
H \times W 问题之后,您的程序将 Q 问题。
对于每个问题,首先, 输出4 整数 Si (1 ≦ Si ≦ H), Sj (1 ≦ Sj ≦ W), Ti (1 ≦ Ti ≦ H), Tj (1 ≦ Tj ≦ W) 用空格分隔。这是dist(Si,Sj,Ti,Tj) 的值是多少? ” 代表问题。
Si Sj Ti Tj
那么你的程序应该是 必须输出 dist(Si,Sj,Ti,Tj) 的值。 一旦您回答了
Q 问题, 您的程序必须立即终止。 如果进程没有结束,则判断结果未定义。
另外,错误输出的结果是未定义的(不一定 WA 可能不一定是这种情况)。
你的程序 如果您正确回答所有 Q 问题,您将被视为回答正确。
请注意,打印后必须刷新输出。如果不冲洗,可能会发生 TLE。
每种语言的输入/输出方法都是过去 AtCoder 问题中提出的问题(链接: ABC 019 D:高桥君和树的直径)可作为参考。