首页 > 代码库 > pku 2425 A Chess Game （SG）
pku 2425 A Chess Game （SG）
题意：
给一个由N个点组成的一张有向图，不存在环。点的编号是0~N-1。
然后给出M个棋子所在的位置（点的编号）【一个点上可同时有多个棋子】。
每人每次可移动M个棋子中的一个棋子一步，移动方向是有向边指向的方向。最后无法移动棋子的人输。
思路：
一眼就可看出的裸的SG，直接看代码吧。
代码：
int sg[1005];vector<int> graph[1005];int dfs(int x){ // position x if(sg[x]!=-1) return sg[x]; int L=graph[x].size(); if(L==0) return sg[x]=0; bool vis[1005] = {0}; rep(i,0,L-1){ vis[dfs(graph[x][i])] = true; } for(int i=0;;++i){ if(!vis[i]) return sg[x]=i; }}int n,Xi,a,m,pos;int main(){ while(scanf("%d",&n)!=EOF){ rep(i,0,n-1) graph[i].clear(); rep(i,0,n-1){ scanf("%d",&Xi); while(Xi--){ scanf("%d",&a); graph[i].push_back(a); } } mem(sg,-1); while(scanf("%d",&m),m){ int ans=0; rep(i,1,m){ scanf("%d",&pos); ans=ans^dfs(pos); } if(!ans) puts("LOSE"); else puts("WIN"); } }}
pku 2425 A Chess Game （SG）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。