14469: 连通块

14469: 连通块

时间限制: 1 Sec   内存限制: 128 MB

题目描述

为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。让小虎拿一块空的围棋盘，随机的在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。
  如下图是一个5*9的一块棋盘，其中'.'表示空格，'*'表示黑棋子,'@'表示白棋子。则有4块连通的棋子块。
.........
..**..@..
.**@@.@@.
..*@..*..
.........
  哥哥大虎在一边看一边想，如果棋盘是N*N的，共放了M个棋子，如何用计算机解决这个问题呢？

输入

第一行两个整数：N M
接下来有M行，每行三个正整数： C X Y (0<=C<=1, 1<=X,Y<=N)。分别表示依次放入棋子的颜色(0表示白色，1表示黑色)、要放入格子的横坐标和格子的纵坐标。

输出

共M行。第i行一个整数，表示放入第i个棋子后，当前有多少个棋子连通块。

样例输入 Copy

【样例1】

3   5

1   1   1

1   1   2

0   2   2

1   3   1

1   2   1

【样例2】

3   5

1   1   2

1   2   1

1   3   2

1   2   3

1   2   2

样例输出 Copy

【样例1】

1

1

2

3

2

【样例2】

1

2

3

4

1

提示

30%数据：1<=N<=10
60%数据：1<=N<=100
100%数据：1<=N<=500   1<=M<=N*N。

解析：

求连通块的题目。可以用dfs,bfs甚至并查集做。这里给出dfs的解法。

每次枚举一下周围四个是否相同，相同且未标记过的点进入循环迭代。

#include<bits/stdc++.h>

using namespace std;

int n,m,c;

int a[505][505];

int jl[505][505];

int read(){

char c=getchar();

while(!isdigit(c)) c=getchar();

int ans=0;

while(isdigit(c)){ans=ans*10+c-'0';c=getchar();}

return ans;

}

void init(){

n=read();m=read();

memset(a,0,sizeof(a));

memset(jl,0,sizeof(jl));

}

bool dfs(int x,int y,int val){

if(x<0||x>n||y<0||y>n) return 0;

if(jl[x][y]==val) return 0;

if(a[x][y]!=c+1) return 0;

jl[x][y]=val;

dfs(x-1,y,val);dfs(x+1,y,val);

dfs(x,y-1,val);dfs(x,y+1,val);

return 1;

}

int main(){

init();

int ans=0;

for(int i=1;i<=m;i++){

int x,y;

ans++;

c=read();x=read();y=read();

if(dfs(x-1,y,i)) ans--;

if(dfs(x+1,y,i)) ans--;

if(dfs(x,y+1,i)) ans--;

if(dfs(x,y-1,i)) ans--;

jl[x][y]=i;a[x][y]=c+1;

printf("%d\n",ans);

}

return 0;

}