【并查集專題】格子游戲
題目描述
Alice和Bob玩了一個古老的游戲：首先畫一個n * n的點陣（下圖n = 3） 接著，他們兩個輪流在相鄰的點之間畫上紅邊和藍邊：
直到圍成一個封閉的圈（面積不必為1）為止，“封圈”的那個人就是贏家，因為棋盤實在是太大了(n <= 200)，他們的游戲實在是太長了！他們甚至在游戲中都不知道誰贏得了游戲，于是請你寫一個程式，幫助他們計算他們是否結束了游戲？
輸入
輸入資料第一行為兩個整數n和m，m表示一共畫了m條線，以后m行，每行首先有兩個數字(x, y)，代表了畫線的起點坐標，接著用空格隔開一個字符，假如字符是"D "，則是向下連一條邊，如果是"R "就是向右連一條邊，輸入資料不會有重復的邊且保證正確，
輸出
輸出一行：在第幾步的時候結束，假如m步之后也沒有結束，則輸出一行“draw”，
樣例輸入
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
樣例輸出
4
資料范圍限制
無
這是一道并查集的題，眾所周知，樹里面是沒有環的，所以在“封圈”之前，棋盤上的畫出來的圖，都是若干棵樹，這道題的重點是如何判斷是否“封圈”，如果要連上的兩個節點都源自同一棵樹（可以是祖先與孩子，也可以是兄弟），那就一定會形成一個環，如果源自不同的樹，那就連起來，因為它們一定不會形成環，
#include<cstdio>
int n,m,f[40005],x,y;
char c;
int find(int x)//查找根節點
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n*n;i++)//初始化
f[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d %c",&x,&y,&c);
int r=(x-1)*n+y,l;//給兩個要連的節點編號
if(c=='D')
l=x*n+y;
else
l=(x-1)*n+y+1;
int X=find(r),Y=find(l);
if(X==Y)//判斷是否源自同一棵樹
{
printf("%d",i);
return 0;
}
else f[X]=Y;
}
printf("draw");
return 0;
}
不見不散
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259325.html
標籤：其他