小贪心

public class Main {
	static int n;
	static int tot=0;
	static int[] white=new int[8];	//该行白皇后放在哪一列
	static int[] black=new int[8];   //该行黑皇后放在哪一列
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		int[][] vi=new int[n][n];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				vi[i][j]=sc.nextInt();
		
		whiteEen(vi,0);
		System.out.println(tot);
	}
	public static void whiteEen(int[][] vi,int cur){
		if(cur==n) blackEen(vi,0);  //白放完开始放黑
		else 
			for(int i=0;i<n;i++){  //枚举列  cur行 i列
				if(vi[cur][i]==0)
					continue;
				else if(check_w(cur,i)){
					white[cur]=i;
					 whiteEen(vi,cur+1);
				}
			}
		
	}
	public static void blackEen(int[][] vi,int cur){
		if(cur==n) tot++;  
		else 
			for(int i=0;i<n;i++){
				if(vi[cur][i]==0 || white[cur]==i)
					continue;
				else if(check_b(cur,i)){
					black[cur]=i;
					blackEen(vi,cur+1);
				}
			}
		
	}
	public static boolean check_w(int x,int y){//检查同列和行列对角线
		for(int k=0;k<x;k++)
			if( y==white[k] ||Math.abs(x-k)==Math.abs(y-white[k]) ) //white[k]-k==y-x || white[k]+k==y+x 可替换Math.abs(x-k)==Math.abs(y-white[k])
				return false;
		return true;
	}
	public static boolean check_b(int x,int y){ //检查同列和行列对角线
		for(int k=0;k<x;k++)
			if( y==black[k] ||Math.abs(x-k)==Math.abs(y-black[k]) ) //black[k]-k==y-x ||  black[k]+k==y+x  同上
				return false;
		return true;
	}
	
}

```

**思路二：**
典型dfs回溯，思路同上，只是用dfs改写
```java

import java.util.Scanner;
public class Main {
	static int cnt = 0;   //计数变量
	static int n =0;
	static int[][] vis= new int[8][8];
	static int[] white=new int[8];	//放在哪一列
	static int[] black=new int[8];   //放在哪一列
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n= in.nextInt();
		  //0表示不能放皇后，1表示可以放皇后，2表示已经放置了白皇后，3表示已经放置了黑皇后
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				vis[i][j]=in.nextInt();
		
		dfs(0);
		System.out.println(cnt);
	}
	static void dfs(int cur)
	{
		if(cur==n) {
			cnt++;
			return ; //
		}
		else
			for(int i=0;i<n;i++){     //试放白皇后
				if(judge(cur,i,2)){
					vis[cur][i]=2;		//一行一行地放置白皇后
					white[cur]=i;    //cur=x  i=y
					for(int j=0;j<n;j++){    // //试放黑皇后
						if(judge(cur,j,3)){
							vis[cur][j]=3;   //一行一行地放置黑皇后
							black[cur]=j; 
							dfs(cur+1);
							vis[cur][j]=1;  //回溯       
						}	
					}
					vis[cur][i]=1;  //回溯 ；  white & black 数组为何无需回溯，因为遍历从0至cur
				}
			}
	}
	static boolean judge(int x,int y,int state)  //state为2时，函数判定白皇后，否则是黑皇后
	{  
		if(vis[x][y]!=1)	return false;
		if(state==2)
			for(int k=0;k<x;k++){   //检查同列和行列对角线  k为x
				if(vis[k][y]==state || white[k]-k==y-x || white[k]+k==y+x)   
					return false; //white[k]-k==y-x  一开始y误写成white[x]，其实white[x]还未确定或用的是之前一波的数据
			}	
		if(state==3)
			for(int k=0;k<x;k++){   //检查同列  k x
				if(vis[k][y]==state || black[k]-k==y-x || black[k]+k==y+x) 
					return false;
			}
		return true;
	}
}
	
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小贪心

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题（Java代码）两种写法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

简单的a+b （C语言代码）

C语言训练-自由落体问题（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

图形输出（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

勾股数（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

小贪心