hdu 1564

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1564

题意：从一个n*n的棋盘的某个角落开始，走过的格子不能再走，每次轮流移动棋子（上下左右），最后无法移动的人输。问是否有先手必胜的策略。

mark：打表后看出规律。证明不会。

代码：

main(n){while(scanf("%d",&n),n)puts(n&1?"ailyanlu":"8600");}

打表程序：

# include <stdio.h>


int n ;
int graph[1010][1010] ;


int dfs (int x, int y)
{
    int xx, yy, i, ans ;
    int tab[4][2] = {-1,0,1,0,0,-1,0,1} ;
    for (i = 0 ; i < 4 ; i++)
    {
        xx = x + tab[i][0] ;
        yy = y + tab[i][1] ;
        if (xx < 0 || xx >= n) continue ;
        if (yy < 0 || yy >= n) continue ;
        if (graph[xx][yy]) continue ;
        graph[xx][yy] = 1 ;
        ans = dfs (xx, yy) ;
        graph[xx][yy] = 0 ;
        if (ans == 0) return 1 ;
    }
    return 0 ;
}


int main ()
{
    graph[0][0] = 1 ;
    for (n = 1 ; n <= 8 ; n++)
        printf ("%d, %d\n", n, dfs (0,0)) ;
}