問題一覧 > 通常問題

No.867 Evacuation Route

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : e869120 / テスター : hirakich1000000007
お気に入りにしたユーザー ProblemId : 3320 / 自分の提出
問題文最終更新日: 2019-08-16 14:48:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 220 (順位表) の他の問題:

Problem Statement

E869120's house is represented by a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i, j)$. The top-left cell is $(1, 1)$, and the bottom-right cell is $(H, W)$.
In his house, the difficulty of movement of cell $(i, j)$ is $A_{i, j}$.
He can move around the house through cells that are vertically or horizontally adjacent.

When a disaster of level $K$ occurs, it takes E869120 the following amount of time to move through cells.

  • Suppose that he passes through cells $(i_1, j_1)$, $(i_2, j_2)$, $(i_3, j_3)$, ..., $(i_G, j_G)$ in this order (including the starting and ending positions).
  • Then, the movement takes $(K^2+A_{i_1,j_1}) + (K^2+A_{i_2,j_2}) + (K^2+A_{i_3,j_3}) + ... + (K^2+A_{i_G,j_G})$ seconds.
  • He cannot pass through the same cell twice.

The emergency exit of his house is at cell $(gx, gy)$. Answer the following $Q$ queries.
  • A disaster of level $k_i$ occurred while E869120 was at cell $(x_i, y_i)$. How many seconds does it take him to reach the emergency exit cell and escape?

Constraints

All input data satisfy the following constraints.

  • $H$ is an integer between $1$ and $250$, inclusive.
  • $W$ is an integer between $1$ and $250$, inclusive.
  • $Q$ is an integer between $1$ and $500 \ 000$, inclusive.
  • $A_{i, j}$ is an integer between $1$ and $99$, inclusive.
  • $x_i$ is an integer between $1$ and $H$, inclusive.
  • $y_i$ is an integer between $1$ and $W$, inclusive.
  • $k_i$ is an integer between $1$ and $1 \ 000 \ 000$, inclusive.
  • $gx$ is an integer between $1$ and $H$, inclusive.
  • $gy$ is an integer between $1$ and $W$, inclusive.

Input

$H$ $W$
$gx$ $gy$
$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$
$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$
...
$A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$
$Q$
$x_1$ $y_1$ $k_1$
$x_2$ $y_2$ $k_2$
$x_3$ $y_3$ $k_3$
...
$x_Q$ $y_Q$ $k_Q$

Output

Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query.

Sample

Sample 1
Input
4 5
1 1
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
5
3 1 1
1 1 7
4 5 3
3 2 5
3 5 2
Output
20
52
102
114
54

In the $1$-st query, consider escaping from cell $(3, 1)$ during a disaster of level $1$.
In this case, by moving along cells $(3, 1)$ -> $(2, 1)$ -> $(1, 1)$, he can escape in $(1^2 + 5) + (1^2 + 9) + (1^2 + 3) = 20$ seconds.

Sample 2
Input
7 7
7 3
1 1 1 1 1 1 1
99 99 99 99 99 99 1
99 1 1 1 1 1 1
99 1 99 99 99 99 99
99 1 1 1 1 1 99
99 99 99 99 99 1 99
99 99 1 1 1 1 99
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
Output
50
125
248
349
430
529
646
781
934
1105
Sample 3
Input
7 7
7 6
1 1 1 1 1 1 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 1 1
2
1 1 4
1 1 5
Output
238
352

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。