872 . 種樹

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

coding_pooh

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

72.7% (8/11)

Tags

ntucpc-speedrun1

Description

王老先生有塊地，這塊地可以用一個 N×M 的表格表示，一開始表格的每個位置都種著一棵高度為 0 的樹。令橫列的編號由上到下，而直排為由左到右，同時令第 i 橫列與第 j 個直排交匯處的格子為 (i,j)。王老先生有很多個生長劑，他可以選擇一個滿足 2≤i≤N−1,2≤j≤M−1 的格子 (i,j) 並在該格子使用，使用後在所有滿足 |x−i|≤1,|y−j|≤1 的格子 (x,y) 的樹高度都會增加 1。

今天早上王老先生用了數個生長劑，但到了下午他卻忘記他在哪些位置使用了生長劑。現在王老先生告訴你每棵樹的高度，你能幫幫他還原出他在每個位置使用了生長劑幾次嗎？

Input Format

輸入第一行有兩個正整數 N,M，代表表格的大小。

接下來 N 行，第 i 行有 M 個數字 ai,1,ai,2,…,ai,M，其中 ai,j 代表格子 (i,j) 上的樹高度。

  • 3≤N≤500
  • 3≤M≤500
  • 0≤ai,j≤106
  • 保證王老先生沒有數錯樹的高度，且生長劑為唯一可以增加樹高度的方法

Output Format

請輸出 N−2 行，第 i 行有 M−2 個整數 bi,1,bi,2,…,bi,M−2，其中 bi,j 代表王老先生在格子 (i+1,j+1) 使用了幾個生長劑。

Sample Input 1

4 5
0 1 3 3 2
1 2 5 4 3
1 2 5 4 3
1 1 2 1 1

Sample Output 1

0 1 2
1 0 1

Sample Input 2

4 3
0 0 0
0 0 0
0 0 0
0 0 0

Sample Output 2

0
0

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
Submit
Back to Top