【題目描述】

Alice和Bob玩了一個(gè)古老的游戲：首先畫一個(gè)n × n的點(diǎn)陣（下圖n = 3）

接著，他們兩個(gè)輪流在相鄰的點(diǎn)之間畫上紅邊和藍(lán)邊：

直到圍成一個(gè)封閉的圈（面積不必為1）為止，“封圈”的那個(gè)人就是贏家。因?yàn)槠灞P實(shí)在是太大了(n ≤ 200)，他們的游戲?qū)嵲谑翘L(zhǎng)了！他們甚至在游戲中都不知道誰贏得了游戲。于是請(qǐng)你寫一個(gè)程序，幫助他們計(jì)算他們是否結(jié)束了游戲？

【輸入】

輸入數(shù)據(jù)第一行為兩個(gè)整數(shù)n和m。m表示一共畫了m條線。以后m行，每行首先有兩個(gè)數(shù)字(x, y)，代表了畫線的起點(diǎn)坐標(biāo)，接著用空格隔開一個(gè)字符，假如字符是"D "，則是向下連一條邊，如果是"R "就是向右連一條邊。輸入數(shù)據(jù)不會(huì)有重復(fù)的邊且保證正確。

【輸出】

輸出一行：在第幾步的時(shí)候結(jié)束。假如m步之后也沒有結(jié)束，則輸出一行“draw”。

【輸入樣例】

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

【輸出樣例】

4

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1000001 #define MOD 123 #define E 1e-6 using namespace std; struct Node{int x;int y; }father[210][210],a,b; Node Find(Node temp) {if(father[temp.x][temp.y].x==temp.x&&father[temp.x][temp.y].y==temp.y)return temp;return father[temp.x][temp.y]=Find(father[temp.x][temp.y]); } int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){father[i][j].x=i;father[i][j].y=j;}for(int i=1;i<=m;i++){int x,y;char ch[10];cin>>x>>y>>ch;if(ch[0]=='D'){a=Find(father[x][y]);b=Find(father[x+1][y]);}else if(ch[0]=='R'){a=Find(father[x][y]);b=Find(father[x][y+1]);}if(a.x==b.x&&a.y==b.y){cout<<i<<endl;return 0;}elsefather[b.x][b.y]=a;}cout<<"draw"<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的格子游戏（信息学奥赛一本通-T1347）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。