当前位置:首页 > 并查集 > 正文
洛谷P5877棋盘游戏[NOI导刊]
48+

题目大意:在一个5*9的棋盘下黑子和白子,这个游戏过程中,各个时刻棋盘上有多少个连通块呢?连通块是指颜色相同的相邻的棋子。

题目描述

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

如下图是一个 $5\times 9$ 的一块棋盘,其中 `.` 表示空格,`*` 表示黑棋子,`@`表示白棋子。

则有 $4$ 块连通子块。
“`
. . . . . . . . .
. . * * . . @ @ .
. * * @ @ . @ @ .
. . * @ . . * . .
. . . . . . . . .
“`

哥哥大虎在一边看一边想,如果棋盘是 $N\times N$ 的,共放了 $M$ 个棋子,如何使用计算机解决这个问题呢?

输入输出格式

输入格式

第一行两个整数:$N,M$。

接下来有 $M$ 行,每行三个整数:$c, x, y$。分别表示依次放入棋子的颜色( $0$ 表示白色,$1$ 表示黑色)、要放入格子的横坐标和格子的纵坐标。

输出格式

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

输入输出样例

输入样例 #1

3 5    
1 1 1  
1 1 2  
0 2 2  
1 3 1  
1 2 1  

输出样例 #1

1 
1 
2 
3 
2

输入样例 #2

3 5
1 1 2
1 2 1
1 3 2
1 2 3
1 2 2

输出样例 #2

1
2
3
4
1

说明

对于 $30\%$ 数据:$1\le N \le 10$。

对于 $60\%$ 数据:$1\le N\le 100$。

对于 $100\%$ 数据:$1\le N\le 500$,$1\le M \le N \times N$,$ 0 \le c \le 1$,$ 1\le x, y \le N$。

解题思路

考察并查集。每下一个棋子,就增加一个连通块;如果这个棋子周围,有同色的棋子块,则合并,减少一块。

程序实现

About

坚决不Copy代码!

本文标签:,,,

洛谷P5877棋盘游戏[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter