Dune II: Battle For Arrakis

题意翻译

题目描述 在一款非常古老、非常流行的策略游戏《Dune II: Battle For Arrakis》中，你到了了最后一项任务。大小为n乘以mn×m的矩形矩阵。最初，有一个a[i,j]。你们部队在单元格里的单位（i，j）（i，j）。 你想为最后的战斗做准备，所以你想把你所有的军队移动到地图的一个单元中（即nm-1 nm−1单元格应包含0个陆军单位，其余单元格应包含整个陆军单位）。 要做到这一点，您可以执行一些（可能是零）步数。在一次移动过程中，您可以从某个单元中选择一个单元，然后将其移动到相邻的相邻单元之一。即从单元（I，j）（I，j）可以将单元移动到单元： （i-1，j）（i）−1，j）； （i，j-1）（i，j−1) ; （i+1，j）（i+1，j）； （i，j+1）（i，j+1）。 当然，你要尽可能快地把你所有的军队转移到一个单元格里。所以，你想知道你需要做的最小移动次数。 并且，当然，生活还在继续，所以地图上的情况发生了变化。有q更新，第i次更新由三个整数x，y，zx，y，z表示。此更新影响单元（x，y）（x，y）中的陆军：此更新后，单元（x，y）（x，y）中的单位数变为z（即用z替换a[x,y]）。 此外，您还需要确定，对于每个i，将整个军队移动到一个单元所需的最小移动次数，并将第一次i更新应用于初始地图。换句话说，第i次更新后的映射等于应用了第一次i次更新的初始映射。 输入格式 输入的第一行包含三个整数n、mn、m和q（1\le n、m\le 1000；1\le q\le 5000 1≤n、 m≤1000;1≤q≤5000）-矩阵的大小和相应的更新次数。 接下来的n n行包含m m个整数，其中第i行中的第j个整数是a[i，j]（1≤a[i,j]≤10^9))-单元中的单元数（i，j）（i，j）。 接下来的q行各包含三个整数，其中第i行包含三个整数x_i，y_i还有z_i（1≤x_i≤n;1≤y_i≤m;1≤z_i≤10^9)-单元数更新的单元以及该单元中相应的新单元数。 输出格式 打印q+1整数r_0，r_1，r_2，…r_n，其中r_0是将所有军队移动到一个单元格中所需的最小移动次数，r_i表示从1到q q的所有i i i是在第一次i更新后将所有军队移动到一个单元格中所需的最小移动次数。

题目描述

You're at the last mission in one very old and very popular strategy game Dune II: Battle For Arrakis. The map of the mission can be represented as a rectangular matrix of size $ n \times m $ . Initially, there are $ a_{i, j} $ units of your army in the cell $ (i, j) $ . You want to prepare for the final battle, so you want to move all your army into exactly one cell of the map (i.e. $ nm-1 $ cells should contain $ 0 $ units of the army and the remaining cell should contain the entire army). To do this, you can do some (possibly, zero) number of moves. During one move, you can select exactly one unit from some cell and move it to one of the adjacent by side cells. I.e. from the cell $ (i, j) $ you can move the unit to cells: - $ (i - 1, j) $ ; - $ (i, j - 1) $ ; - $ (i + 1, j) $ ; - $ (i, j + 1) $ . Of course, you want to move all your army into exactly one cell as fast as possible. So, you want to know the minimum number of moves you need to do that. And, of course, life goes on, so the situation on the map changes. There are $ q $ updates, the $ i $ -th update is denoted by three integers $ x, y, z $ . This update affects the army in the cell $ (x, y) $ : after this update, the number of units in the cell $ (x, y) $ becomes $ z $ (i.e. you replace $ a_{x, y} $ with $ z $ ). Also, you want to determine, for each $ i $ , the minimum number of moves needed to move your entire army into exactly one cell with the first $ i $ updates applied to the initial map. In other words, the map after the $ i $ -th update equals the initial map with the first $ i $ updates applied to it.

输入输出格式

输入格式

The first line of the input contains three integers $ n, m $ and $ q $ ( $ 1 \le n, m \le 1000; 1 \le q \le 5000 $ ) — the size of the matrix and the number of updates correspondingly. The next $ n $ lines contain $ m $ integers each, where the $ j $ -th integer in the $ i $ -th line is $ a_{i, j} $ ( $ 1 \le a_{i, j} \le 10^9 $ ) — the number of units in the cell $ (i, j) $ . The next $ q $ lines contain three integers each, where the $ i $ -th line contains three integers $ x_i, y_i $ and $ z_i $ ( $ 1 \le x_i \le n; 1 \le y_i \le m; 1 \le z_i \le 10^9 $ ) — the cell in which the number of units updates and the new number of units in this cell correspondingly.

输出格式

Print $ q+1 $ integers $ r_0, r_1, r_2, \dots, r_n $ , where $ r_0 $ is the minimum number of moves you need to move all your army into exactly one cell, and $ r_i $ for all $ i $ from $ 1 $ to $ q $ is the minimum number of moves you need to move all your army into exactly one cell after the first $ i $ updates.

输入输出样例

输入样例 #1

3 3 1
1 2 3
2 1 2
1 1 2
2 3 100

输出样例 #1

21 22

输入样例 #2

4 4 3
2 5 6 3
4 8 10 5
2 6 7 1
8 4 2 1
1 1 8
2 3 4
4 4 5

输出样例 #2

123 135 129 145