Description

Figure 1	Figure 2	Figure 3a	Figure 3b	Figure 4

Your task is to decide if a specified sequence of moves in the board game Twixt ends with a winning move.

In this version of the game, different board sizes may be specified. Pegs are placed on a board at integer coordinates in the range [0, N]. Players Black and White use pegs of their own color. Black always starts and then alternates with White, placing a peg at one unoccupied position (x,y). Black‘s endzones are where x equals 0 or N, and White‘s endzones are where y equals 0 or N. Neither player may place a peg in the other player‘s endzones. After each play the latest position is connected by a segment to every position with a peg of the same color that is a chess knight‘s move away (2 away in one coordinate and 1 away in the other), provided that a new segment will touch no segment already added, except at an endpoint. Play stops after a winning move, which is when a player‘s segments complete a connected path between the player‘s endzones.

For example Figure 1 shows a board with N=4 after the moves (0,2), (2,4), and (4,2). Figure 2 adds the next move (3,2). Figure 3a shows a poor next move of Black to (2,3). Figure 3b shows an alternate move for Black to (2,1) which would win the game.

Figure 4 shows the board with N=7 after Black wins in 11 moves:
(0, 3), (6, 5), (3, 2), (5, 7), (7, 2), (4, 4), (5, 3), (5, 2), (4, 5), (4, 0), (2, 4).

Input

Output

Sample Input

4 50 2 2 4 4 2 3 2 2 34 50 2 2 4 4 2 3 2 2 17 110 3 6 5 3 2 5 7 7 2 4 45 3 5 2 4 5 4 0 2 40 0

Sample Output

noyesyes

Source

黑白棋的游戏，在n*n的棋盘上，黑棋先手，且最后一步是黑棋。当黑棋从x=0连接的到x=n，时黑棋获胜，问最后一步是不是致胜的一步

每个点都可以和它周围的八个点连接，类似象棋中的马，但是在连接两个点的时候，在连线之间不能有其他的连线（包括黑棋自身的连线）。所以在连接一条线的时候，要判断其他的可能会切割这条线的九条线是否存在。

先判断不包含最后一步的黑棋能不能胜利，再判断加上最后一步后能不能获胜，如果开始不能获胜，后来获胜，那么输出yes，否则，输出no

#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std ;int vis[500] ;int Map[25][25] , c[500][500] ;//ºÚΪ1£¬°×Ϊ-1queue <int> que ;void solve1(int i,int j,int n,int temp){    if( (i-1) >= 0 && (i+1) < n && (j-1) >= 0 && c[ (i-1)*n+j ][ (i+1)*n+(j-1) ] != 0 )        return ;    if( (i-1) >= 0 && (j-2) >= 0 && (i+1) < n && (j-1) >= 0 && c[ (i-1)*n+(j-2) ][ (i+1)*n+(j-1) ] != 0 )        return ;    if( (j-3) >= 0 && (i+1) < n && (j-1) >= 0 && c[ i*n+(j-3) ][ (i+1)*n+(j-1) ] != 0 )        return ;    if( (j-1) >= 0 && (i+1) < n && (j+1) < n && c[ i*n+(j-1) ][ (i+1)*n+(j+1) ] != 0 )        return ;    if( (j-1) >= 0 && (i+2) < n && c[ i*n+(j-1) ][ (i+2)*n+j ] != 0 )        return ;    if( (j-1) >= 0 && (i+2) < n && (j-2) >= 0 && c[ i*n+(j-1) ][ (i+2)*n+(j-2) ] != 0 )        return ;    if( (i-1) >= 0 && (j-1) >= 0 && (i+1) < n && c[ (i-1)*n+(j-1) ][ (i+1)*n+j ] != 0 )        return ;    if( (i+1) < n && (j-2) >= 0 && c[ (i+1)*n+j ][ i*n+(j-2) ] != 0 )        return ;    if( (j-2) >= 0 && (i+2) < n && (j-1) >= 0 && c[ i*n+(j-2) ][ (i+2)*n+(j-1) ] != 0 )        return ;    c[ i*n+j ][ (i+1)*n+(j-2) ] = c[ (i+1)*n+(j-2) ][ i*n+j ] = temp ;    return ;}void solve2(int u,int v,int n,int temp){    if( (u-1) >= 0 && (v-1) >= 0 )    {        if( (u+1) < n && c[ (u-1)*n+(v-1) ][ (u+1)*n+v ] != 0 ) return ;        if( (u+1) < n && (v-2) >= 0 && c[ (u-1)*n+(v-1) ][ (u+1)*n+(v-2) ] != 0 ) return ;        if( (v-3) >= 0 && c[ (u-1)*n+(v-1) ][ u*n+(v-3) ] != 0 ) return ;    }    if( (v-1) >= 0 )    {        if( (u-1) >= 0 && (v+1) < n && c[ u*n+(v-1) ][ (u-1)*n+(v+1) ] != 0 ) return ;        if( (u-2) >= 0 && c[ u*n+(v-1) ][ (u-2)*n+v ] != 0 ) return ;        if( (u-2) >= 0 && (v-2) >= 0 && c[ u*n+(v-1) ][ (u-2)*n+(v-2) ] != 0 ) return ;    }    if( (u+1) < n && (v-1) >= 0 && (u-1) >= 0 && c[ (u+1)*n+(v-1) ][ (u-1)*n+v ] != 0 ) return ;    if( (u-1) >= 0 && (v-2) >= 0 && c[ (u-1)*n+v ][ u*n+(v-2) ] != 0 ) return ;    if( (v-2) >= 0 && (u-2) >= 0 && (v-1) >= 0 && c[ u*n+(v-2) ][ (u-2)*n+(v-1) ] != 0 ) return ;    c[ u*n+v ][ (u-1)*n+(v-2) ] = c[ (u-1)*n+(v-2) ][ u*n+v ] = temp ;    return ;}void solve3(int u,int v,int n,int temp){    if( (u+1) < n )    {        if( (u-1) >= 0 && (v-1) >= 0 && c[ (u+1)*n+v ][ (u-1)*n+(v-1) ] != 0 ) return ;        if( (v-2) >= 0 && c[ (u+1)*n+v ][ u*n+(v-2) ] != 0 ) return ;        if( (u+2) < n && (v-2) >= 0 && c[ (u+1)*n+v ][ (u+2)*n+(v-2) ] != 0 ) return ;    }    if( (u+1) < n && (v-1) >= 0 )    {        if( (v+1) < n && c[ (u+1)*n+(v-1) ][ u*n+(v+1) ] != 0 ) return ;        if( (u+2) < n && (v+1) < n && c[ (u+1)*n+(v-1) ][ (u+2)*n+(v+1) ] != 0 ) return ;        if( (u+3) < n && c[ (u+1)*n+(v-1) ][ (u+3)*n+v ] != 0 ) return ;    }    if( (u+1) < n && (v+1) < n && (v-1) >= 0 && c[ (u+1)*n+(v+1) ][ u*n+(v-1) ] != 0 ) return ;    if( (v-1) >= 0 && (u+2) < n && c[ u*n+(v-1) ][ (u+2)*n+v ] != 0 ) return ;    if( (u+2) < n && (u+1) < n && (v-2) >= 0 && c[ (u+2)*n+v ][ (u+1)*n+(v-2) ] != 0 ) return ;    c[ u*n+v ][ (u+2)*n+(v-1) ] = c[ (u+2)*n+(v-1) ][ u*n+v ] = temp ;    return ;}void solve4(int u,int v,int n,int temp){    if( (u-1) >= 0 )    {        if( (u-2) >= 0 && (v-2) >= 0 && c[ (u-1)*n+v ][ (u-2)*n+(v-2) ] != 0 ) return ;        if( (v-2) >= 0 && c[ (u-1)*n+v ][ u*n+(v-2) ] != 0 ) return ;        if( (u+1) < n && (v-1) >= 0 && c[ (u-1)*n+v ][ (u+1)*n+(v-1) ] != 0 ) return ;    }    if( (u-1) >= 0 && (v-1) >= 0 )    {        if( (u-3) >= 0 && c[ (u-1)*n+(v-1) ][ (v-3)*n+v ] != 0 ) return ;        if( (u-2) >= 0 && (v+1) < n && c[ (u-1)*n+(v-1) ][ (u-2)*n+(v+1) ] != 0 ) return ;        if( (v+1) < n && c[ (u-1)*n+(v-1) ][ u*n+(v+1) ] != 0 ) return ;    }    if( (u-1) >= 0 && (v+1) < n && (v-1) >= 0 && c[ (u-1)*n+(v+1) ][ u*n+(v-1) ] != 0 ) return ;    if( (v-1) >= 0 && (u-2) >= 0 && c[ u*n+(v-1) ][ (u-2)*n+v ] != 0 ) return ;    if( (u-2) >= 0 && (v-2) >= 0 && c[ (u-2)*n+v ][ (u-1)*n+(v-2) ] != 0 ) return ;    c[ u*n+v ][ (u-2)*n+(v-1) ] = c[ (u-2)*n+(v-1) ][ u*n+v ] = temp ;    return ;}int bfs(int u,int n){    int v , i , j ;    while( !que.empty() ) que.pop() ;    vis[u] = 1 ;    que.push(u) ;    while( !que.empty() )    {        u = que.front() ;        que.pop() ;        if( u >= (n-1)*n )            return 1 ;        for(i = 0 ; i < n*n ; i++)        {            if( c[u][i] == 1 && vis[i] == 0 )            {                vis[i] = 1 ;                que.push(i) ;            }        }    }    return 0 ;}void solve(int temp,int n){    int u , v ;    scanf("%d %d", &u, &v) ;    Map[u][v] = temp ;    if( (u+1) < n && (v-2) >= 0 && Map[u][v] == Map[u+1][v-2] )        solve1(u,v,n,temp);    if( (u-1) >= 0 && (v+2) < n && Map[u][v] == Map[u-1][v+2] )        solve1(u-1,v+2,n,temp) ;    if( (u-1) >= 0 && (v-2) >= 0 && Map[u][v] == Map[u-1][v-2] )        solve2(u,v,n,temp) ;    if( (u+1) < n && (v+2) < n && Map[u][v] == Map[u+1][v+2] )        solve2(u+1,v+2,n,temp) ;    if( (u+2) < n && (v-1) >= 0 && Map[u][v] == Map[u+2][v-1] )        solve3(u,v,n,temp) ;    if( (u-2) >= 0 && (v+1) < n && Map[u][v] == Map[u-2][v+1] )        solve3(u-2,v+1,n,temp) ;    if( (u-2) >= 0 && (v-1) >= 0 && Map[u][v] == Map[u-2][v-1] )        solve4(u,v,n,temp) ;    if( (u+2) < n && (v+1) < n && Map[u][v] == Map[u+2][v+1] )        solve4(u+2,v+1,n,temp) ;}int main(){    int n , m , x , y , u , v , temp , i , j ;    while( scanf("%d %d", &n, &m) != EOF )    {        if( m == 0 && n == 0 ) break ;        n++ ;        memset(Map,0,sizeof(vis)) ;        memset(c,0,sizeof(c)) ;        temp = 1 ;        m-- ;        while( m-- )        {            solve(temp,n) ;            temp = -temp ;        }        int k1 = 0 , k2 = 0 ;        memset(vis,0,sizeof(vis)) ;        for(j = 0 ; j < n ; j++)        {            if(  Map[0][j] == 1 && vis[j] == 0 )            {                k1 = bfs(j,n) ;                if( k1 == 1 ) break ;            }        }        solve(temp,n) ;        memset(vis,0,sizeof(vis)) ;        for(j = 0 ; j < n ; j++)        {            if(  Map[0][j] == 1 && vis[j] == 0 )            {                k2 = bfs(j,n) ;                if( k2 == 1 ) break ;            }        }        if( k1 == 0 && k2 == 1)            printf("yes\n") ;        else            printf("no\n") ;    }    return 0;}

poj--2706--Connect(极限大模拟)