1674: 水果消除

时间限制: 2 Sec  内存限制: 128 MB
提交: 335  解决: 164
[提交][状态][讨论版]

题目描述

“水果消除”是一款手机游戏,相信大家都玩过或玩过类似的游戏。

下面是“水果消除”游戏的一种初始状态。

消除的基本规则:如果有2个或2个以上的相同水果连在一起,则可以点选并消除。

请问在某一种状态下,有几种可以点选并消除的选择方案。

HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP

例如,对于上图所示的初始状态,将有6种点选并消除的选择方案。这6种方案依次如下图所示。

HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP         HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP          HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP

HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP          HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP          HNUSTOJ-1674  水果消除(搜索或并查集)-LMLPHP

输入

先输入一个整数n,表示放水果的格子总数为n*n。n取3到1000之间的整数(含3和1000)。

然后依次输入n*n个表示水果的数据,不同的水果用不同的数字表示,同一种水果用相同的数字表示。

表示水果的数字编号从1开始,不超过100。

输出

在输入数据对应的初始状态下,有几种点选并消除的选择方案。

输出方案数。

样例输入

6
1 1 2 2 2 2
1 3 2 1 1 2
2 2 2 2 2 3
3 2 3 3 1 1
2 2 2 2 3 1
2 3 2 3 2 2

样例输出

6

提示

 

来源

这道题可以直接DFS求连通块,也可以标号以后并查集;求连通块的时候要注意包含的格子至少为两个计数才加一;
DFS求连通块:

#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; const int N = + ;
int mat[N][N];
bool visit[N][N];
int cur;
void DFS(int i,int j,int n,int color){
if(i< || j< || i>=n || j>=n) return;
if(visit[i][j]) return;
if(mat[i][j]!=color) return;
visit[i][j] = true;
cur++;
DFS(i+,j,n,color);
DFS(i-,j,n,color);
DFS(i,j+,n,color);
DFS(i,j-,n,color);
} int DFS_AL(int n){
int Count=;
memset(visit ,,sizeof(visit));
for(int i=;i<n;i++)
for(int j=;j<n;j++)
if(!visit[i][j]){
cur=;
DFS(i,j,n,mat[i][j]);
if(cur>)
Count++;
}
return Count;
} void Input_data(int n){
for(int i=;i<n;i++)
for(int j=;j<n;j++)
scanf("%d",&mat[i][j]);
} int main(){
int n;
scanf("%d",&n);
Input_data(n);
printf("%d\n",DFS_AL(n));
}

并查集:

#include<cstdio>
#include<queue> using namespace std; const int MaxSize = +;
struct node1
{
int p;
int num;
}pre[MaxSize*MaxSize]; const int dir[][]= {{,},{,-},{,},{-,}};
short mat[MaxSize][MaxSize];
bool visit[MaxSize][MaxSize];
int Find(int x)
{
return pre[x].p==x?x:(pre[x].p=Find(pre[x].p));
} void Merge(int x,int y)
{
x= Find(x),y=Find(y);
if(x!=y)
{
pre[y].p=x;
pre[x].num += pre[y].num;
}
}
int main()
{
int n,i,j,k=,ans,h;
scanf("%d",&n);
for(i=; i<n; i++)
for(j=; j<n; j++)
{
scanf("%hd",&mat[i][j]);
pre[i*n+j].p=k++;
pre[i*n+j].num=;
visit[i][j]=false;
}
for(i=; i<n; i++)
for(j=; j<n; j++)
{
if(!visit[i][j])
{
visit[i][j] = true;
for(h=; h<; h++)
if(i+dir[h][]>= && i+dir[h][]<n && j+dir[h][]>= && j+dir[h][]<n )
if(mat[i][j] == mat[i+dir[h][]][j+dir[h][]])
Merge((i*n+j),((i+dir[h][])*n+j+dir[h][]));
}
}
for(ans=,i=; i<k; i++)
if(pre[i].p==i && pre[i].num > )
ans++;
printf("%d\n",ans);
}

//如有错误,还请留言指出
05-28 08:37