题目链接：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;
}
速度挺不错的：
就这样了。。。