方格染色

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给你一个n×m的地图,地图上每一个小格子种都是一个数字x,表示格子的属性,对于相邻(八个方向)的同属性的格子可以组成一个联通块。现在在地图的上方有一只蚂蚁,它想走到地图的下方,它可以四个方向走(上下左右),但是小明不想让蚂蚁走到下方,他知道蚂蚁不走染色的格子,每次小明可以选择一个联通块,将其染色,染色的花费为联通块的大小。小明想知道最少花费多少才能使得蚂蚁不能走到下方。

Input

多组输入,每组先输入n,m。表示方格的大小。1<=n,m<=30,
接下来是n行每行m个数表示小方格的属性。1<=x<=5

Output

输出最少的花费

Sample Input

1 2
3 5
5 6
5 4 2 4 5 4
3 5 5 4 1 3
4 4 3 5 5 3
2 4 5 2 4 1
2 5 4 2 3 5

Sample Output

2
7

Hint

Source

2016暑假集训结训赛 by JueChen