The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

NOJ 1177 跳马 SG函数,博弈

先贴个代码,博弈问题还要继续深究,special thanks to thinkking!
原题:


Input


Output


SampleInput

2
5 2
2 2
2 3
5 2
3 3
2 3

SampleOutput

Case 1: Alice
Case 2: Bob

#include<iostream>
#include
<cmath>
using namespace std;

int n,m;
int dir[2][2]={{-1,-2},{-2,-1}};

bool god(int x,int y)
{
    
if(x<1||x>500||y<1||y>500)
        
return false;
    
return true;
}

int const maxn=510;
int SG[maxn][maxn];

struct node
{
    
int x,y;
}
q[20020];

int v[3];
int main()
{

    
int ca;
    scanf(
"%d",&ca);
    
int cn=0;
    
for(int i=1;i<=500;i++)
    
{
        
for(int j=1;j<=500;j++)
        
{
            memset(v,
0,sizeof(v));
            
for(int k=0;k<2;k++)
            
{

                
int nx=i+dir[k][0];
                
int ny=j+dir[k][1];
                
if(god(nx,ny))
                
{
                    v[SG[nx][ny]]
=1;
                }

            }

            
for(int k=0;k<=2;k++)
            
{
                
if(v[k]==0)
                
{
                    SG[i][j]
=k;
                    
break;
                }

            }


        }

    }

    
while(ca--)
    
{
        cn
++;
        scanf(
"%d%d",&n,&m);
        
for(int i=1;i<=m;i++)
            scanf(
"%d%d",&q[i].x,&q[i].y);
        
        
int ans=0;
        
for(int i=1;i<=m;i++)
        
{
            ans
^=SG[q[i].x][q[i].y];
        }

        
if(ans)
            printf(
"Case %d: Alice\n",cn);
        
else
            printf(
"Case %d: Bob\n",cn);
    }

    
return 0;
}

posted on 2010-07-13 20:48 abilitytao 阅读(1331) 评论(3)  编辑 收藏 引用

评论

# re: NOJ 1177 跳马 SG函数,博弈 2010-07-16 11:16 明王不动

看不懂题目,怎么样才算赢?  回复  更多评论   

# re: NOJ 1177 跳马 SG函数,博弈[未登录] 2010-07-16 14:48 abilitytao

@明王不动
就是走日嘛
123
456
6可以到1

12
34
56
6可以到1  回复  更多评论   

# re: NOJ 1177 跳马 SG函数,博弈 2010-07-18 22:02 abilitytao

@明王不动
如果一方不能再移动任何马,说明此方失败。  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理