hdu DIY FLIGHT GAME (dfs)

2023-01-05 23:09:28

FLIGHT GAME

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 41 Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

越前龙马跟手冢国光pk飞行棋，但由于两人棋（yun）力(qi)相当，一直未能分出胜负，所以他们决定修改飞行棋的规则继续战斗。
他们将棋子由多个改成了一个，即两人轮流移动一个棋子，棋子初始时放在固定起点处，每次移动一格，龙马先走，谁先不能移动就算输，樱乃还是一如既往的支持越前，但还是心有担忧，棋盘可以看成一个有向无环图，现告诉你棋盘以及起点位置，假设龙马和手冢都选择最优策略，问越前能否赢的这场

Input

多组数据，每组数据的第一行三个数1<=n<=100,1<=m<=1000,1<=st<=n表示点数，边数，起点位置。
接下来m行给定棋盘，每行两个数x,y表示x可以移动到y，保证棋盘符合一个有向无环图，且节点编号。

Output

每组数据输出一行，若越前胜利输出”Yes”,否则输出”No”.

Sample Input

Sample Output

No

Author

yanglei9211

某个人出的题，不过觉得还有点意思，于是就写一下解题报告

题意是中文，应该算是博弈题吧，不过要用搜索解决，应为数据不大，可以直接遍历整个图。思想也不难，不过也想了挺久的，主要在判断走到某个根节点时谁胜谁负，然后处理一下子节点=0，=1，>1的情况就行了。

 //62 MS    264 KB    Visual C++

 #include<iostream>

 #include<vector>

 using namespace std;

 vector<int>V[];

 int dfs(int u,int cnt)

 {

     int m=V[u].size();

     if(m==) return cnt&;

     if(m==) return dfs(V[u][],cnt+);

     int flag=cnt&;

     for(int i=;i<m;i++){

         if(flag^dfs(V[u][i],cnt+))

             return ;

     }

     return ;

 }

 int main(void)

 {

     int n,m,st;

     int a,b;

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

     {

         for(int i=;i<=n;i++) V[i].clear();

         for(int i=;i<m;i++){

             scanf("%d%d",&a,&b);

             V[a].push_back(b);

         }

         if(dfs(st,)) puts("Yes");

         else puts("No");

     }

     return ;

 }

 /*

 10 12 1

 1 2

 1 3

 2 4

 3 4

 4 5

 4 6

 5 7

 6 7

 7 8

 7 9

 8 10

 9 10

 */

码农公寓