#P18825. [Croatian CPC2017] Ploča
[Croatian CPC2017] Ploča
[Croatian CPC2017] Ploča
题目描述
Mirko 有一块 米的土地,被铺成 个 米的方格。地面并不平整,每块地砖都有自己的高度,单位为厘米。
两块地砖若有一条公共边,就称为相邻。如果可以从一块地砖出发,每次移动到与当前地砖相邻且高度相同的地砖,最终到达另一块地砖,就称这两块地砖连通。
暴风雨中的冰块落到某块地砖上时,会使这块地砖以及当前与它连通的所有地砖的高度同时降低 厘米。冰块依次落下,每次只落到一块地砖上。地砖高度和连通关系会随着这些操作改变。
求最少需要落下多少块冰,才能使所有地砖的高度相同。你可以自由选择每块冰落到的位置。
输入格式
第一行包含两个整数 ()。
接下来 行,每行包含 个整数,依次表示该行各地砖的初始高度。每个高度均在 内。
输出格式
输出一个整数,表示所需冰块数量的最小值。
样例 1
输入
3 3
3 3 2
2 3 3
2 3 1
输出
2
样例说明
第一次让冰块落到中央的地砖上,除右下角外,所有地砖都会变成高度 。再让一块冰落到中央,全部地砖便都变成高度 。