【DFS】蓝桥杯试题 填字母游戏_蓝桥杯 填字母游戏 dfs

题目描述

OJ地址 http://lx.lanqiao.cn/problem.page?gpid=T450

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：
　　“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。

K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。

并且：

1. 轮到某人填的时候，只能在某个空格中填入L或O
　　2. 谁先让字母组成了“LOL”的字样，谁获胜。
　　3. 如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

输入：

第一行，数字n（n<10），表示下面有n个初始局面。
　　接下来，n行，每行一个串，表示开始的局面。
　　比如：“**”, 表示有6个空格。“L”, 表示左边是一个字母L，它的右边是4个空格。

输出：

要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。
　　1 表示能赢
　　-1 表示必输
　　0 表示可以逼平

样例输入1：

4
***
L**L
L**L***L
L*****L
1
2
3
4
5

样例输出1：

0
-1
1
1
1
2
3
4

思路：

简单的博弈类问题，写出来不难，但是好像蓝桥杯对运行时间卡的挺严的。看一下最后AC的结果

一开始也用了记忆化搜索了，但是只给了60分，剩下两个测试点都是超时，后来看见一个人写的代码，仔细比对，逻辑上没有问题，但是我的就是超时，一点点修改，发现了问题，一开始我的程序如下：

#include <bits/stdc++.h>

using namespace std;

map<string,int> vis;
string sc;

int game(string sc){
	if(vis.count(sc)){
		return vis[sc];
	}

	if(sc.find("LOL") != -1){
		//找到了
		return -1; 
	}
	
	if(sc.find("*") == -1){
		// 没有空格 
		return 0;
	}
	bool ping = false;
	for(unsigned int i = 0 ; i < sc.size();i++){
		
		if(sc[i] == '*'){
			string tmp = sc;
			tmp[i] = 'L';
			int f = game(tmp);

			if(f == -1){
				return vis[sc] = 1;
			}else if(f == 0){
				ping = true;
			}
				
			tmp[i] = 'O';
			f = game(tmp);

			if(f == -1){
				return vis[sc] = 1;
			}else if(f == 0){
				ping = true;
			}
					
		}
		
	}

	if(ping){
		return vis[sc] = 0;
	}
	return vis[sc] = -1;
}

int main(){
	int n;
	scanf("%d",&n);
	string str;
	for(int i = 0; i < n; i++){
		cin >> str;
		cout << game(str) << endl;
	}
	

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

和人家的进行比对，发现相差的一点就是，我的dfs函数的参数string sc这个字符串，他放在了全局变量的位置，我试了一下，果真！在全局变量中就AC了，最后的AC代码在下边。貌似全局变量的操作比参数效率要高？

代码

#include <bits/stdc++.h>

using namespace std;

map<string,int> vis;
string sc;

int game(){
	if(vis.count(sc)){
		return vis[sc];
	}

	if(sc.find("LOL") != -1){
		//找到了
		return -1; 
	}
	
	if(sc.find("*") == -1){
		// 没有空格 
		return 0;
	}
	bool ping = false;
	for(unsigned int i = 0 ; i < sc.size();i++){
		
		if(sc[i] == '*'){
			
			sc[i] = 'L';
			int f = game();
			sc[i] = '*';
			if(f == -1){
				return vis[sc] = 1;
			}else if(f == 0){
				ping = true;
			}
				
			sc[i] = 'O';
			f = game();
			sc[i] = '*';
			if(f == -1){
				return vis[sc] = 1;
			}else if(f == 0){
				ping = true;
			}
					
		}
		
	}

	if(ping){
		return vis[sc] = 0;
	}
	return vis[sc] = -1;
	
	
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		cin >> sc;
		cout << game() << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65