Java实现洛谷 P6183 [USACO10MAR]The Rock Game S（DFS）

灰太狼 2023-07-21 03:21 211阅读 0赞

## P6183 \[USACO10MAR\]The Rock Game S ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70 1]

输入输出样例
    输入  
    3
    输出  
    OOO
    OXO
    OXX
    OOX
    XOX
    XXX
    XXO
    XOO
    OOO

PS：  
因为每一位只有两种可能，这里用01，有没有重复的，就可以把01转换成十进制，  
看看有没有用过，知道找出所有

## `Java代码：90分还望大佬指点` ##

import java.util.Scanner;
    
    public class TheRockGame { 
    	public static int n=0,max=0;;
    	public static int[] num;;
    // public static int[][] result;;
    	public static boolean[] bool;;
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		n=sc.nextInt();
    		sc.close();
    		num = new int [n];
    		//一位的可能是2种，也就是2的n次方可能
    		max=1<<n;
    		bool = new boolean [max];
    // result=new int [max+1][n];
    		bool[0]=true;
    		//第一种肯定全是O
    		for (int i = 0; i <n; i++) { 
    			System.out.print('O');
    		}
    		System.out.println();
    		dfs(1);
    	}
    	public static void dfs(int step){ 
    		//如果是最后一步的话，肯定是O了
    		if(step==max){ 
    			for (int i = 0; i <n; i++) { 
    				System.out.print('O');
    			}
    			System.out.println();
    // outPut();
    			System.exit(0);
    		}
    		for (int i = 0; i < num.length; i++) { 
    			//每一次只改一位的，因为我每一步只能进行一次操作
    			num[i]=num[i]==1?0:1;
    			int temp=toBinary();
    			//如果我当前的数被用过，就跳过
    			if(bool[temp]){ 
    				num[i]=num[i]==1?0:1;
    				continue;
    			}
    			//没有被用过的话，就记录用过
    			bool[temp]=true;
    			//输出此次的
    			for (int j = 0; j < n; j++) { 
    // System.out.print(num[j]==1?'X':'O');
    // result[step][j]=num[j];
    				System.out.print(num[j]==1?'X':'O');
    			}
    			System.out.println();
    			//只有找到新的才能到下一步
    			dfs(step+1);
    			//用完了复原
    			bool[temp]=false;
    			num[i]=num[i]==1?0:1;
    			
    		}
    	}
    // public static void outPut(){ 
    // for (int i = 0; i <= bool.length; i++) { 
    // for (int j = 0; j < n; j++) { 
    // System.out.print(result[i][j]==1?'X':'O');
    // }
    // System.out.println();
    // 
    // }
    // }
    	//从二进制转换过来
    	public static int toBinary(){ 
    		int sum=0;
    		for (int i = 0; i <n; i++) { 
    			sum=sum*2+num[i];
    		}
    		return sum;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70]: /images/20230528/c4c6dc18587644fb9970b03a042cb124.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70 1]: /images/20230528/471fb0e0f81543bfb86445d5dd18972c.png