题意：一个棋盘，摆了四种颜色的棋子，每次选择一个棋子消掉，同时跟它相连的也会被消掉，之后
1）下方有空的棋子会往下掉，填补空的格子
2）如果有整列被消的掉的，该列右边的棋子全部往左移，当然，左移的界限就是到被消掉的一整列，这个看Sample就知道了
分析：棋盘不大，6*6而已。
一开始的感觉就是迭代加深搜索了，再搜的过程中，优先选择相连颜色中数量最多消掉，31ms，不过爆搜也可以过，600+ms
View Code
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int M = 8;
int g[M][M],gg[M][M],n,m,ans;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[M][M];
int num;
struct node
{
int x,y,num,ord;
node(int a=0,int b=0,int c=0,int d=0):x(a),y(b),num(c),ord(d){}
};
struct node1
{
int x,y;
node1(int a=0,int b=0):x(a),y(b){}
};
queue<node1> Q;
bool cmp(node a,node b)
{
if(a.num!=b.num)
return a.num>b.num;
return a.ord<b.ord;
}
bool check()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(gg[i][j])
return false;
return true;
}
void change()//调整消掉后的棋盘
{
int emp[8]={0};
for(int j=0;j<m;j++)//调整每一列
{
for(int i=n-1;i>=0;i--)
{
if(!gg[i][j])
{
int t=i;
while(gg[i][j]==0 && i>=0)
i--;
if(i>=0){
gg[t][j]=gg[i][j];
gg[i][j]=0;
i=t;
}
}
}
int tt=0;
for(int i=0;i<n;i++)
if(gg[i][j]==0)
tt++;
else break;
if(tt==n) emp[j]=1;//标记整行消掉的列
}
for(int j=0,flag=0;j<m-flag;j++)//若存在整行消掉的列，则调整
{
if(!emp[j])
continue;
for(int i=0;i<n;i++)
{
for(int k=j-flag+1;k<m-flag;k++)
gg[i][k-1]=gg[i][k];
gg[i][m-1-flag]=0;
}
flag++;
}
}
void dfs2(int x,int y,int key)//找出连通块中的相同颜色的个数
{
num++;
vis[x][y]=true;
for(int k=0;k<4;k++)
{
int i=x+dir[k][0];
int j=y+dir[k][1];
if(i<0 || i>=n || j<0 || j>=m || gg[i][j]!=key || vis[i][j])
continue;
dfs2(i,j,key);
}
}
void BFS(int x,int y)//将同一个连通块消掉
{
Q.push(node1(x,y));
bool vis1[8][8]={0};
vis1[x][y]=true;
while(!Q.empty())
{
node1 temp=Q.front();
Q.pop();
for(int k=0;k<4;k++)
{
int i=temp.x+dir[k][0];
int j=temp.y+dir[k][1];
if(i<0 || i>=n || j<0 || j>=m || vis1[i][j] || gg[i][j]!=gg[x][y])
continue;
vis1[i][j]=true;
gg[i][j]=0;
Q.push(node1(i,j));
}
}
gg[x][y]=0;
}
bool dfs(int step)
{
if(check()&&ans==step)
return true;
if(step>ans) return false ;
int map[8][8];
memset(vis,0,sizeof(vis));
memcpy(map,gg,sizeof(gg));
node dd[36];
int cnt=0;
for(int j=0;j<m;j++)//类似于那个h（）函数的过程吧，求出每一个连通块中相同颜色的个数
for(int i=n-1;i>=0;i--)//试了一下，这个遍历的顺序影响不大
{
if(!vis[i][j] && map[i][j]!=0)
{
num=0;
dfs2(i,j,map[i][j]);
dd[cnt]=node(i,j,num,cnt);
cnt++;
}
}
sort(dd,dd+cnt,cmp);
for(int i=0;i<cnt;i++)//排序后，将相同颜色最多的块消掉
{
memcpy(gg,map,sizeof(map));
BFS(dd[i].x,dd[i].y);
change();
if(dfs(step+1))
return true;
}
return false;
}
int main()
{
while(scanf("%d %d",&n,&m)==2)
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&g[i][j]);
memcpy(gg,g,sizeof(g));
if(check())
{
printf("0\n");
continue;
}
ans=1;
while(true)
{
if(dfs(0))
break;
memcpy(gg,g,sizeof(g));//这里忘记把棋盘变回来了，找了好久的错
ans++;
}
printf("%d\n",ans);
}
return 0;
}