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

Alexandra ·

更新时间:2024-09-20

· 767 次阅读

P6183 [USACO10MAR]The Rock Game S

在这里插入图片描述

输入输出样例
输入  
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;
	}
}

作者：南墙

p6 JAVA dfs

1024 个赞