【u232】圍棋游戲

2019-11-14 09:17:16

字體：大中小

來源：轉載

供稿：網友

Time Limit: 1 second Memory Limit: 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個棋子后，當前有多少個棋子連通塊。

【數據規模】

30%數據：1<=n<=10 60%數據：1<=n<=100 100%數據：1<=m<=n*n。n<=500。

Sample Input1

3 5 1 1 1 1 1 2 0 2 2 1 3 1 1 2 1 Sample Output1

1 1 2 3 2

Sample Input2

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

Sample Output2

1 2 3 4 1

【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=u232

【題意】中文題

【題解】每次放下棋子之后,連通塊遞增1; 看看放下去的棋子所在的位置的四周有沒有和它的顏色相同的棋子; 如果有的話,用并查集的找爸爸函數看看它們倆是不是連在一起的,如果不是連在一起的則把它們連在一起; 然后連通塊遞減1; 然后輸出答案就好; (x,y)坐標可以一一對應一個線性的數字->(x-1)*n+y; 【完整代碼】

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 510;int n,m,a[MAXN][MAXN],cnt = 0;int f[MAXN*MAXN];int change(int x,int y){ return (x-1)*n+y;}int ff(int x){ if (f[x]==x) return x; else return f[x] = ff(f[x]);}int main(){ //freopen("F://rush.txt","r",stdin); memset(a,255,sizeof a); rei(n);rei(m); rep1(i,1,m) { int c,x,y; rei(c);rei(x);rei(y); a[x][y] = c; cnt++; int temp = change(x,y); f[temp] = temp; int xx = -1,yy =-1; rep1(j,1,4) { int tx,ty; tx = x+dx[j]; ty = y+dy[j]; if (tx<0 || tx>n) continue; if (ty<0 || ty>n) continue; if (a[tx][ty]==a[x][y]) { xx = tx,yy = ty; int temp2 = change(xx,yy); int r1 = ff(temp2),r2 = ff(temp); if (r1!=r2) { f[r1] = r2; cnt--; } } }