CodeForces Gym 100500A A. Poetry Challenge DFS

题目链接:

http://codeforces.com/gym/100500/attachments

题意:

文字接龙，谁接不下去了，就算谁输输出赢家
都很聪明的情况下

题解:

看起来是博弈不会啊这个dfs还不懂
qsc ls：转化成图论之后，直接DFS爆搜就好了！

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e4+10;
17 
18 int n,m,vis[30],flag;
19 char s1[11][maxn],s2[11][maxn];
20 vector<int> e[30];
21 
22 bool dfs(int x){
23 
24     for(int i=0; i<(int)e[x].size(); i++){
25         int v = e[x][i];
26         if(vis[v]) continue;
27         vis[v] = 1;
28         if(!dfs(v)){  // 返回了0 说明对于v 对手已经没有接的了  对当前玩家x来说 是不利的 不能选以v的开头为尾的x
29             vis[v] = 0;
30             return 1; // 返回1 对于上一层的这个点是不行的  就要选下一个点（如果有）
31         }
32     }
33 
34     return 0;  // 返回0表示 x的对手没有可以接的了， win
35 }
36 
37 int main(){
38     int T=read();
39     for(int cas=1; cas<=T; cas++){
40         for(int i=0; i<=25; i++) e[i].clear();
41         MS(vis);
42         flag = 0;
43         n=read();
44         for(int i=0; i<n; i++)
45             gets(s1[i]);
46         m = read();
47         for(int i=0; i<m; i++)
48             gets(s2[i]);
49         for(int i=0; i<n; i++){
50             int len = strlen(s1[i]);
51             for(int j=0; j<m; j++)
52                 if(s1[i][len-1] == s2[j][0])
53                     e[i].push_back(j+9);
54         }
55 
56         for(int j=0; j<m; j++){
57             int len = strlen(s2[j]);
58             for(int i=0; i<n; i++)
59                 if(s2[j][len-1] == s1[i][0])
60                     e[j+9].push_back(i);
61         }
62 
63         for(int i=0; i<n; i++){
64             vis[i] = 1;
65             if(!dfs(i)){
66                 flag = 1;
67                 break;
68             }
69             vis[i] = 0;
70         }
71         if(flag) cout << "Game " << cas << ": player1
";
72         else cout << "Game " << cas << ": player2
";
73     }
74 
75     return 0;
76 }
77 
78 //http://codeforces.com/gym/100500/attachments