B. Sleepy Game 博弈搜索
2024-10-09 03:14:10
题意:给一个有向图和起点,然后只有一名选手,这名选手可以随意挪动棋子,最终不能动的时候走过的边为奇数边为Win并输出路径,否则如果有环输出Draw,否则输出Lose;
知道状态数最多只有n*2就可以了,分成先后手考虑。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+;
int vis[N][],top,nxt[N],n,m,x,y,p,to[N],H[N],tot;
bool cir;
int nt[N][];
bool dp[N][];
void add(int u,int v){
++tot;nxt[tot]=H[u];to[tot]=v;H[u]=tot;
}
void dfs(int now,int k){
bool ko=;
if(vis[now][k]==-) return;
vis[now][k]=;
for(int i=H[now];i;i=nxt[i]){
int v=to[i];
ko=;
if((vis[v][k^]==)|(vis[v][k]==)) cir=;
if(vis[v][k^]==) continue;
dfs(v,k^);
if(!k) {
if(!dp[v][k^]) dp[now][k]=,nt[now][k]=v;
}
else {
if(dp[v][k^]) dp[now][k]=,nt[now][k]=v;
}
}
if(!ko) dp[now][k]=;
vis[now][k]=-;
}
void print(int p,int k){
if(!p) {puts("");return;}
printf("%d ",p),print(nt[p][k],k^);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) dp[i][]=;
for(int i=;i<=n;++i) {
scanf("%d",&x);
while(x--) {
scanf("%d",&y);
add(i,y);
}
}
scanf("%d",&p);
dfs(p,);
if(dp[p][]) puts("Win"),print(p,);
else if(cir) puts("Draw");
else puts("Lose");
}
最新文章
- 在UPDATE中更新TOP条数据以及UPDATE更新中使用ORDER BY
- matlab 求解线性方程组之范数
- JavaScript的面向对象编程(OOP)(一)——类
- Spring IoC源码解读——谈谈bean的几种状态
- SVN 远程无法联通
- 人工免疫算法-python实现
- [转]Python中的矩阵转置
- 编程基础-msdn编程指南笔记
- 【特殊的图+DP】【11月校赛】大家一起玩游戏
- 奇葩问题:spring+mybaits项目突然出现其中一些Mapper类找不到
- MBProgressHUD 问题
- 工作小结(关于webpack)
- Django 1.11 release note简明解读
- java之SpringMVC配置!配置!配置!
- Mysql-自带的一些功能,基本用法(视图,触发器,事务,存储过程,函数,流程控制)
- Java-IO流之输入输出流基础示例
- To be taught if i am fortunate
- PhoenixFD插件流体模拟——UI布局【Dynamics】详解
- C语言入坑指南-被遗忘的初始化
- Python模块定义和使用