poj 2425 A Chess Game

题意:给你一个有向无环图,再给你图上的棋子,每人每次只能移动一个棋子,当轮到你不能移动棋子是就输了,棋子可以同时在一个点

比赛时就差这题没ak,做了几天博弈终于搞懂了.

#include <iostream>

#include <cstdio>

#include<vector>

#include<cstring>

using namespace std;

#define N 1010

vector<int> adj[N];

int sg[N],n;

int mex(int v){

	bool vis[N]={0};

	int i,w;

	for(i=0;i<adj[v].size();i++){

		w=adj[v][i];

		if(sg[w]==-1)

			sg[w]=mex(w);

		vis[sg[w]]=1;

	}

	for(i=0;;i++)

		if(vis[i]==0)

			return i;

}

int main(int argc, char** argv) {

	int m,v,w,sum;

	while(scanf("%d",&n)!=EOF){

		for(v=0;v<n;v++){

			adj[v].clear();

			scanf("%d",&m);

			while(m--){

				scanf("%d",&w);

				adj[v].push_back(w);

			}

		}

		memset(sg,-1,sizeof(sg));

		while(scanf("%d",&m)!=EOF&&m){

			sum=0;

			while(m--){

				scanf("%d",&v);

				if(sg[v]==-1)

					sg[v]=mex(v);

					sum^=sg[v];

			}

			if(sum)

				printf("WIN\n");

			else

				printf("LOSE\n");

		}

	}

	return 0;

}

巴特西

poj 2425 A Chess Game_sg函数

最新文章

热门文章