填字母游戏(博弈问题)

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**L
L**L***L
L*****L


则程序应该输出：
0
-1
1

1

解这道题用到博弈问题的递归思路。

小明填一个字母后，让大师去填字母，大师如果输了，代表小明填这个位置能赢。

判断所有小明可以填的位置 *    只要 有一个位置 能让小明赢，小明就赢了

如果判断到了最后，小明都赢不了，需要判断这些位置中出现过平局没有。

有平局，小明 平局，没有平局小明只能输

这道题难点：不同于其他博弈问题，存在平局。

考虑平局问题，最好的结果，小明赢，否则判断能不能平局，不能平局，只能输。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) { 
    	Scanner input = new Scanner(System.in);
    	int n = input.nextInt();
    	while(--n>=0){
    		String in = input.next();
    		System.out.println(f(in.toCharArray()));
    	}
    	
    	
    }  
    
    public static int f(char[] arr){
    	String s = new String(arr);
    	//如果LOL已经出现了那么说明已经输了
    	if(s.contains("LOL"))return -1;
    	
    	//如果不存在可以填写的位置说明平局
    	if(!s.contains("*"))return 0;
    	
    	//用来记录平局出现过没有？
    	boolean ping = false;
    	
    	
    	//模拟所有可以填字母的位置
    	for(int i=0;i<arr.length;i++){
    		//不可以填字母跳过
    		if(arr[i]!='*')continue;
    		
    		
    		//这里之所以使用try finally 因为，finally可以在return 之前执行，方便了回溯
    		try {
    			//模拟填入L
    			arr[i] = 'L';
				switch (f(arr)) {
				//如果返回值为-1 说明 我填写字母后，下一个人 输了，他输了我肯定赢
				case -1:
					return 1;
				//出现平局
				case 0:
					ping = true;
					break;
				}
				
				//模拟填入O
				arr[i] = 'O';
				switch (f(arr)) {
				case -1:
					return 1;
				case 0: 
					ping = true;
					break;
				}
			} finally {
				//回溯，这个位置还变成*
				arr[i] = '*';
			}
    	}
    	
    	//存在平局。
    	return ping?0:-1;
    }
    
    
    
}  

刚刚的问题存在 重复数据递归 。使用动态规划减少运算量。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) { 
    	Scanner input = new Scanner(System.in);
    	int n = input.nextInt();
    	while(--n>=0){
    		String in = input.next();
    		System.out.println(f(in.toCharArray()));
    	}
    	
    	
    }  
    
    //缓存
    static Map<String,Integer> cache = new HashMap<String,Integer>();
    
    public static int f(char[] arr){
    	String s = new String(arr);
    	
    	//判断该过程是否出现
    	if(cache.containsKey(s)){
    		return cache.get(s);
    	}
    	
    	//如果LOL已经出现了那么说明已经输了
    	if(s.contains("LOL")){
    		cache.put(s, -1);
    		return -1;
    	}
    	
    	//如果不存在可以填写的位置说明平局
    	if(!s.contains("*")){
    		cache.put(s, 0);
    		return 0;
    	}
    	
    	//用来记录平局出现过没有？
    	boolean ping = false;
    	
    	
    	//模拟所有可以填字母的位置
    	for(int i=0;i<arr.length;i++){
    		//不可以填字母跳过
    		if(arr[i]!='*')continue;
    		
    		
    		//这里之所以使用try finally 因为，finally可以在return 之前执行，方便了回溯
    		try {
    			//模拟填入L
    			arr[i] = 'L';
    			
				switch (f(arr)) {
				//如果返回值为-1 说明 我填写字母后，下一个人 输了，他输了我肯定赢
				case -1:
					//存放该过程
					cache.put(s,1);
					return 1;
				//出现平局
				case 0:
					ping = true;
					break;
				}
				
				//模拟填入O
				arr[i] = 'O';
				switch (f(arr)) {
				case -1:
					//存放该过程
					cache.put(s,1);
					return 1;
				case 0: 
					ping = true;
					break;
				}
			} finally {
				//回溯，这个位置还变成*
				arr[i] = '*';
			}
    	}
    	
    	//存在平局。
    	return ping?0:-1;
    }
    
    
    
}  

学习简单的博弈问题：

点击我

动态规划：

点击我