題目連結：http://poj.org/problem?id=2706
這道題很水，真的很水。。。一看就知道不斷加點加邊，維護一個黑棋的并查集就可以了。
唯一的難點在于判斷目前這一步與哪些點可以連接配接：
觀察可發現，一條線隻有兩個連通方向：從左下連到右上，或從右上連到左下。
如下圖：綠色的線為目前要判斷連通的點，黃色的線為與它在同一行（列）的三種截斷它的情況，其連通方向與綠色相反。再看左邊的那一個格子，綠線占據了上方的半個格子，是以上方的兩條紫色的線都可以截斷它，而下方隻有藍色的那條與它連通方向相反的線截斷它。同理，可推得右邊的格子。
再将這種情況拓展一下，我們就得到了目前這條線可以連通的條件為：
①與它所在的日字格子在同一行（列），即方向相同的三個日字格子中，沒有與它的連通方向相反的線存在。
②與它所在的日字格子互相垂直的兩個日字格子中，與它在同一方向的格子中沒有已經連通的線，與它在不同方向的格子中沒有與它的連通方向相反的線。（目前格子的方向即為線處于這個格子的哪個方位）
于是，我們就可以暴力判斷了。
每加一個點，我們就判斷它能否與已有的邊連通，若能，則連通。若為黑色點，則維護并查集。
用一個v[x1][y1][x2][y2][2]來維護邊的連通情況：v[x1][y1][x2][y2][0]代表目前格子從左上到右下的連通情況，v[x1][y1][x2][y2][1]代表目前格子從左下到右上的連通情況。（注意：這裡的x1，y1，x2，y2指的是格子的列标與行标，而不是棋子所在的點的坐标）這樣就可以友善地判斷目前的線是否能夠連通。
虛拟一個左端點與一個右端點，維護黑色棋子的連通情況，若加完點後左右相通，則黑棋獲勝，否則黑棋敗。（題目保證不會在最後一步前出現獲勝情況，并且各步棋都是合法的）
判斷目前棋子與哪些點可以連通有很多種方法，本人用的最暴力的O（m²）的方法，空間什麼的也可以優化，因為一個日字格隻有一種連通方式，并且周圍的格子的連通也可以用它來表示，但因為在考試，是以本人沒有去研究什麼高大上的判斷與記錄連通的方法，簡簡單單地寫了四種情況，以後有時間再去研究一下高大上的判斷方法。我在網上看到很多題解都是用的BFS，于是就想發一個并查集吧，代碼如下：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
/*
關鍵在于判斷目前的線是否可以連接配接。
v[x1][y1][x1+1][y1][0]表示目前格子的左上到右下是否連接配接
v[x1][y1][x1+1][y1][1]表示目前格子的左下到右上是否連接配接
v[x1][y1][x1][y1+1][0]表示目前格子的左上到右下是否連接配接
v[x1][y1][x1][y1+1][1]表示目前格子的左下到右上是否連接配接
*/
int n,m,LEFT=0,RIGHT;
int v[25][25][25][25][2];
int x[250+10],y[250+10],fa[250+10];
int find(int x)//并查集不說了吧
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void check(int fi,int x1,int y1,int li,int x2,int y2)
{
if(x2<x1)//保證x1在左邊，友善判斷
{
int t=x1;x1=x2;x2=t;
t=y1;y1=y2;y2=t;
}
if(x1+1==x2)//日字格豎着的情況
{
if(y1+2==y2)
{
//連通方式為1，與目前點在同一列的情況
if(v[x1+1][y1+1][x1+1][y2][0])return;
if(v[x1+1][y2][x1+1][y2+1][0])return;
if(v[x1+1][y1][x1+1][y1+1][0])return;
//與前一個格子垂直的情況
if(v[x1][y1+1][x1+1][y1+1][1])return;
if(v[x1][y1+1][x1+1][y1+1][0])return;
if(v[x1+1][y1+1][x1+2][y1+1][0])return;
//與後一個格子垂直的情況
if(v[x1+1][y1+2][x1+2][y1+2][1])return;
if(v[x1+1][y1+2][x1+2][y1+2][0])return;
if(v[x1][y1+2][x1+1][y1+2][0])return;
//可連通，連通
v[x1+1][y1+1][x1+1][y1+2][1]=1;
v[x1+1][y1+2][x1+1][y1+1][1]=1;
//為黑色格子，維護并查集
if(fi%2)
{
fa[find(fi)]=find(li);
}
}
if(y1-2==y2)
{
//連通方式為0，與目前點在同一列的情況
if(v[x1+1][y2+1][x1+1][y2+2][1])return;
if(v[x1+1][y2][x1+1][y2+1][1])return;
if(v[x1+1][y1][x1+1][y1+1][1])return;
//與前一個格子垂直的情況
if(v[x1][y1][x1+1][y1][1])return;
if(v[x1][y1][x1+1][y1][0])return;
if(v[x1+1][y1][x1+2][y1][1])return;
//與後一個格子垂直的情況
if(v[x1+1][y1-1][x1+2][y1-1][1])return;
if(v[x1+1][y1-1][x1+2][y1-1][0])return;
if(v[x1][y1-1][x1+1][y1-1][1])return;
//可連通，連通
v[x1+1][y1-1][x1+1][y1][0]=1;
v[x1+1][y1][x1+1][y1-1][0]=1;
//為黑色格子，維護并查集
if(fi%2)
{
fa[find(fi)]=find(li);
}
}
}
else if(x1+2==x2)//日字格橫着的情況
{
if(y1+1==y2)
{
//連通方式為1，與目前點在同一行的情況
if(v[x1+1][y1+1][x1+2][y1+1][0])return;
if(v[x1][y1+1][x1+1][y1+1][0])return;
if(v[x2][y1+1][x2+1][y1+1][0])return;
//與前一個格子垂直的情況
if(v[x1+1][y1][x1+1][y1+1][1])return;
if(v[x1+1][y1][x1+1][y1+1][0])return;
if(v[x1+1][y1+1][x1+1][y1+2][0])return;
//與後一個格子垂直的情況
if(v[x2][y2][x2][y2+1][1])return;
if(v[x2][y2][x2][y2+1][0])return;
if(v[x2][y2-1][x2][y2][0])return;
//可連通，連通
v[x1+1][y1+1][x1+2][y1+1][1]=1;
v[x1+2][y1+1][x1+1][y1+1][1]=1;
//為黑色格子，維護并查集
if(fi%2)
{
fa[find(fi)]=find(li);
}
}
if(y1-1==y2)
{
//連通方式為0，與目前點在同一行的情況
if(v[x1+1][y2+1][x1+2][y2+1][1])return;
if(v[x1][y2+1][x1+1][y2+1][1])return;
if(v[x2][y2+1][x2+1][y2+1][1])return;
//與前一個格子垂直的情況
if(v[x1+1][y1][x1+1][y1+1][1])return;
if(v[x1+1][y1][x1+1][y1+1][0])return;
if(v[x1+1][y1-1][x1+1][y1][1])return;
//與後一個格子垂直的情況
if(v[x2][y2][x2][y2+1][1])return;
if(v[x2][y2][x2][y2+1][0])return;
if(v[x2][y2+1][x2][y2+2][1])return;
//可連通，連通
v[x1+1][y1][x1+2][y1][0]=1;
v[x1+2][y1][x1+1][y1][0]=1;
//為黑色格子，維護并查集
if(fi%2)
{
fa[find(fi)]=find(li);
}
}
}
}
void work(int sx,int sy,int id)
{
//這個是暴力枚舉的以前的點，其實可以開個map數組儲存一下
//這樣每次隻要枚舉八個方向就可以了
for(int i=1;i<id;i++)
{
if(i%2==id%2)check(id,sx,sy,i,x[i],y[i]);//相同顔色才check
//傳遞編号，因為黑棋需要維護并查集
}
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(n==0&&m==0)break;
memset(v,0,sizeof(v));//初始化連通圖
for(int i=1;i<=m;i++)fa[i]=i;//初始化并查集
fa[LEFT]=LEFT;RIGHT=m+1;fa[RIGHT]=RIGHT;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
if(i%2)//黑棋，維護并查集
{
if(x[i]==0)fa[find(i)]=find(LEFT);
if(x[i]==n)fa[find(i)]=find(RIGHT);
}
work(x[i],y[i],i);//判連通
}
if(find(LEFT)==find(RIGHT))printf("yes\n");//左右連通，win
else printf("no\n");//否則false
}
return 0;
}
速度挺不錯的：
就這樣了。。。