先贴个代码,博弈问题还要继续深究,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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[2][2]=
{
{-1,-2},
{-2,-1}};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool god(int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(x<1||x>500||y<1||y>500)
return false;
return true;
}
int const maxn=510;
int SG[maxn][maxn];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x,y;
}q[20020];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int v[3];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ca;
scanf("%d",&ca);
int cn=0;
for(int i=1;i<=500;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int j=1;j<=500;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(v,0,sizeof(v));
for(int k=0;k<2;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int nx=i+dir[k][0];
int ny=j+dir[k][1];
if(god(nx,ny))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
v[SG[nx][ny]]=1;
}
}
for(int k=0;k<=2;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(v[k]==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
SG[i][j]=k;
break;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
while(ca--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}