文章目录
问题描述输入格式输出格式样例输入样例输出解题思路：解题代码：问题描述
小明经常玩 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 表示可以逼平
样例输入
4***L**LL**L***LL*****L
样例输出
0
-1
1
1
解题思路：
对于给出的字符串进行深搜回溯，尝试每一种走法，如果碰到能赢的走法则返回1。如果碰到平局和输的情况则继续尝试，直到尝试完每一种走法。为了防止超时，我们可以对深搜过程中的结果进行记录；在每一次深搜前都检查一下是否深搜过这个字符串，如果有记录则直接返回结果，不必再一次进行深搜。这样可以提高效率。
解题代码：
import java.util.HashMap;import java.util.Scanner;public class 填字母游戏 {//用于记录深搜过程中得到的结果static HashMap<String, Integer> map = new HashMap<String, Integer>();public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] s = new int[n]; //用于存储结果for(int i=0; i<n; i++){s[i] = dfs(scanner.next());}//打印结果for(int i=0; i<n; i++){System.out.println(s[i]);}}/** 用记忆型递归进行深搜尝试每一种走法*/private static int dfs(String str) {//如果曾经对这个字符串进行过深搜，则把记录的结果直接返回，不用再一次进行深搜，提高效率if(map.containsKey(str)) return map.get(str);//如果轮到自己走的时候已经形成LOL， 则表示自己已经输了if(str.contains("LOL")) return -1;//如果字符串的长度不到3，或者是字符串中已经没有*，则表示平局if(str.length()<3 || !str.contains("*")) return 0;int res = -1;char[] arr = str.toCharArray();//尝试当前的每一种走法for(int i=0; i<arr.length; i++){if(arr[i] == '*'){//表示当前位置能下arr[i] = 'L'; //尝试当前位置写L//要对dfs()的返回值取相反数，因为自己走完一步就轮到对方走一步// 对方输了就是自己赢了，如果是对方赢了则进行下一种尝试res = Math.max(res, -dfs(new String(arr)));if(res == 1){//如果写L能赢break;}else{arr[i] = 'O';res = Math.max(res, -dfs(new String(arr)));if(res == 1) break; //如果写O能赢}arr[i] = '*'; //回溯}}map.put(str, res); //记录本次深搜的结果return res;}}
