题目描述

为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。让小虎拿一块空的围棋盘，随机的在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一都有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。

如下图是一个5×9的一块棋盘，其中“.”表示空格，“×”表示黑棋子，“@”表示白棋子。则有4块连通的棋子块。

......... ..**..@.. .**@@.@@. ..*@..*.. .........

哥哥大虎在一边看一边想，如果棋盘是N×N的，共放了M个棋子，如何用计算机解决这个问题呢？

输入输出格式

输入格式：

第一行，两个整数，N，M；

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

输出格式：

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

输入输出样例

输入样例一：

3 51 1 11 1 20 2 21 3 11 2 1

输出样例一：

11232

输入样例二：

3 51 1 21 2 11 3 21 2 31 2 2

输出样例二：

12341

说明

数据规模：

对于30%的数据，1≤N≤10；

对于60%的数据，1≤N≤100；

对于100%的数据，1≤N≤500，1≤M≤N×N。

 

思路：硬搜会超时，只需判断放置棋子的四周是否有同色棋子，如无则++。

#include
      
       #include
       
        using namespace std; int dx[4]={
    1,0,-1,0},dy[4]={
    0,1,0,-1};int col,n,m,x,y,ans,a[505][505],b[505][505]; bool dfs(int x,int y,int p){    if(x<1||x>n||y<1||y>n||b[x][y]==p||a[x][y]!=col)return false;    b[x][y]=p;     for(int i=0;i<4;i++)dfs(x+dx[i],y+dy[i],p);     return true; }int main(){    scanf("%d%d",&n,&m);     for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&col,&x,&y);         col++;        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--;        ans++;        b[x][y]=i;        a[x][y]=col;        printf("%d\n",ans);     }     return 0;}