Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)
程序员文章站
2024-01-07 20:44:40
...
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;
}
}