#P18825. [Croatian CPC2017] Ploča

[Croatian CPC2017] Ploča

[Croatian CPC2017] Ploča

题目描述

Mirko 有一块 R×SR\times S 米的土地,被铺成 R×SR\times S 个 1×11\times1 米的方格。地面并不平整,每块地砖都有自己的高度,单位为厘米。

两块地砖若有一条公共边,就称为相邻。如果可以从一块地砖出发,每次移动到与当前地砖相邻且高度相同的地砖,最终到达另一块地砖,就称这两块地砖连通。

暴风雨中的冰块落到某块地砖上时,会使这块地砖以及当前与它连通的所有地砖的高度同时降低 11 厘米。冰块依次落下,每次只落到一块地砖上。地砖高度和连通关系会随着这些操作改变。

求最少需要落下多少块冰,才能使所有地砖的高度相同。你可以自由选择每块冰落到的位置。

输入格式

第一行包含两个整数 R,SR,S(2≤R,S≤10002\le R,S\le1000)。

接下来 RR 行,每行包含 SS 个整数,依次表示该行各地砖的初始高度。每个高度均在 [1,109][1,10^9] 内。

输出格式

输出一个整数,表示所需冰块数量的最小值。

样例 1

输入

3 3
3 3 2
2 3 3
2 3 1

输出

2

样例说明

第一次让冰块落到中央的地砖上,除右下角外,所有地砖都会变成高度 22。再让一块冰落到中央,全部地砖便都变成高度 11。