欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)

程序员文章站 2024-01-07 20:44:40
...

P6183 [USACO10MAR]The Rock Game S

Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)

Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)

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

相关标签: 洛谷

上一篇:

下一篇: