1 #include<iostream>
  2 #include<stdio.h>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<queue>
  6 using namespace std;
  7 
  8 struct node
  9 {
 10     int a[7][7];
 11     int step;
 12 }start;
 13 struct st
 14 {
 15     int x,y;
 16 };
 17 int n,m;
 18 int to[4][2]={ {1,0},{0,1},{0,-1},{-1,0} };
 19 bool use[7][7];
 20 bool hash[7][7];
 21 queue<node>Q;
 22 queue<st>S;
 23 
 24 void Init_use(node &t)
 25 {
 26     int i,j;
 27     for(i=1;i<=n;i++)
 28         for(j=1;j<=m;j++)
 29             if(t.a[i][j]==0)use[i][j]=true;
 30             else use[i][j]=false;
 31 }
 32 bool pd(node &t)
 33 {
 34     int i,j;
 35     bool flag=true;
 36     for(i=1;i<=n;i++)
 37         for(j=1;j<=m;j++)
 38             if(t.a[i][j]!=0)flag=false;
 39     return flag;
 40 }
 41 void change(node &t)
 42 {
 43     int i,j;
 44     int tmp[7][7],k,s;
 45     bool flag;
 46 
 47     for(i=1;i<=n;i++)
 48     {
 49         for(j=1;j<=m;j++)
 50             if(!use[i][j] && hash[i][j])
 51             {
 52                 use[i][j]=true;
 53                 t.a[i][j]=0;
 54             }
 55     }
 56     memset(tmp,0,sizeof(tmp));
 57     for(i=1;i<=m;i++)
 58     {
 59         k=n;
 60         for(j=n;j>=1;j--)
 61             if(t.a[j][i]>0)
 62                 tmp[k--][i]=t.a[j][i];
 63     }
 64     memset(t.a,0,sizeof(t.a));
 65     for(i=1,s=1;i<=m;i++)
 66     {
 67         flag=true;
 68         for(j=1;j<=n;j++) if(tmp[j][i]!=0){flag=false;break;}
 69         if(flag)continue;
 70         for(j=1;j<=n;j++)
 71             t.a[j][s]=tmp[j][i];
 72         s++;
 73     }
 74 }
 75 void bfs(int x,int y,node t,int num)
 76 {
 77     int i;
 78     st ans,cur;
 79     memset(hash,false,sizeof(hash));
 80     while(!S.empty())
 81     {
 82         S.pop();
 83     }
 84     ans.x=x;
 85     ans.y=y;
 86     S.push(ans);
 87     hash[x][y]=true;
 88 
 89     while(!S.empty())
 90     {
 91         cur=S.front();
 92         S.pop();
 93 
 94         for(i=0;i<4;i++)
 95         {
 96             ans=cur;
 97             ans.x=ans.x+to[i][0];
 98             ans.y=ans.y+to[i][1];
 99             if(ans.x>=1&&ans.x<=n && ans.y>=1&&ans.y<=m && !hash[ans.x][ans.y])
100             {
101                 if(t.a[ans.x][ans.y]==num)
102                 {
103                     hash[ans.x][ans.y]=true;
104                     S.push(ans);
105                 }
106             }
107         }
108     }
109 }
110 void dbfs()
111 {
112     int i,j;
113     node cur,t;
114     Q.push(start);
115     while(!Q.empty())
116     {
117         cur=Q.front();
118         Q.pop();
119 
120         if(pd(cur)==true)
121         {
122             printf("%d\n",cur.step);
123             return;
124         }
125         Init_use(cur);
126 
127         for(i=1;i<=n;i++)
128             for(j=1;j<=m;j++)
129             {
130                 if(use[i][j]==false && cur.a[i][j]!=0)
131                 {
132                     t=cur;
133                     bfs(i,j,t,cur.a[i][j]);
134                     change(t);
135                     t.step++;
136                     Q.push(t);
137                 }
138             }
139     }
140 }
141 int main()
142 {
143     int i,j;
144     while(scanf("%d%d",&n,&m)>0)
145     {
146         for(i=1;i<=n;i++)
147             for(j=1;j<=m;j++)
148                 scanf("%d",&start.a[i][j]);
149         start.step=0;
150         while(!Q.empty())
151         {
152             Q.pop();
153         }
154         dbfs();
155     }
156     return 0;
157 }