)
{
return sg[x]=i;
}
}
}
int main()
{
int n,sum;
mem(sg,-1);
while(scanf("%d",&n)!=EOF)
{
sum=dfs(n);
if(sum)
{
printf("1\n");
}
else
{
printf("2\n");
}
}
return 0;
}
POJ2599 A funny game
记忆化搜索，这题的博弈味道不浓，更多的是搜索。题意是给一个图，两人轮流移动，走过的节点不能再走。水题，dfs+标记就行。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int n,v[1001][1001],vis[1001];
int dfs(int x)
{
int i;
FOR(1,n,i)
{
vis[x]=1;
if(v[i][x]&&!vis[i])
{
if(!dfs(i))
{
vis[x]=0;
return i;
}
}
vis[x]=0;
}
return 0;
}
int main()
{
int m,i,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
mem(v,0);
mem(vis,0);
FOR(1,n-1,i)
{
RD(a);
RD(b);
v[a][b]=v[b][a]=1;
}
i=dfs(m);
if(i!=0)
{
printf("First player wins flying to airport %d\n",i);
}
else
{
printf("First player loses\n");
}
}
return 0;
}