小哈哈

用户名：20180390139

访问量：19776

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6374
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”
浏览：305

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：399

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

蓝桥杯基础练习VIP-2n皇后问题-题解(详细代码）---------典型的递归回溯

　　作者: 小哈哈　　　　发表时间：2019-07-24 10:54:36 浏览：706　|　评论：0　

原题链接：蓝桥杯基础练习VIP-2n皇后问题

//这里把黑色皇后叫做“黑色小哈”，白色的叫“白色小哈”
    
    #include<stdio.h>
    #define N 100
    int e[N][N]={0},n;
    void dfs(int i);
    int ok(int x,int y);    //其实跟8皇后差不多，得看看这个位置“小哈”能不能站 
    int sum=0;
    int main(){
    	int i,j;
    
    	scanf("%d",&n);
    	for(i=1;i<=n;i++){
    		for(j=1;j<=n;j++){
    			scanf("%d",&e[i][j]);
    		}
    	}
    
    	dfs(1);     
    	printf("%d\n",sum);
    	return 0;
    }
    void dfs(int i){    //跟八皇后问题一样，一行一行地排 ，先排第1行再第2行 ........
                        //下面有j2和j3循环就是看  在这一行里  小哈门是怎么“站位置”的 
    	if(i==n+1){   //如果从第一行排到了第n+1行，那么也就是前面n行已经排好了，到n+1行就结束了 
    		
    		sum++;
    		return ;
    	}
    
    	int flag=0;
    	int j2,j3;
    	for(j2=1;j2<=n;j2++){    //j2控制“黑色小哈”的纵坐标让“黑色小哈”先排 
    
    		flag=ok(i,j2);     //看看 “黑色小哈”能不能站（i,j2)这个位置 
    		if(flag!=0){
    			if(flag==2||flag==1)  //ok这个函数有返回值0,1,2,3    
    				e[i][j2]=2;	    //0代表不能放，2代表可以放黑色小哈，3代表可以放白色小哈，1代表两种小哈都能放 
    			else
    				continue ;       //如果不能站，就 (j2++)往右边再走一个位置，目的是先让“黑色小哈”站好再让“白色小哈站 ” 
    		}
    		else
    			continue ; //跟上面一句话的注释是一样的，总之是先让“黑色小哈”站好再让“白色小哈”站 
    
    
           //****###上面的循环是为了放“黑色小哈”，如果那个位置能放它就放好它
    	   //然后在来到这下面的###代码#### 
    		for(j3=1;j3<=n;j3++){   //好了， “黑色小哈”一旦站好，就看看“白色小哈”怎么站 
    
    		  flag=ok(i,j3);   //同样的道理  看看这个位置能不能放“白色小哈” 
    		  if(flag!=0){    //但是ok函数前面已经说了它有0,1,2,3这四个返回值，每个返回值代表的意思不一样 
    			  if(flag==3||flag==1){  //如果ok的返回值为3，代表这个位置只能放“白色小哈"如果返回1，则代表黑白小哈都能放 
    				  e[i][j3]=3;   //表示这个位置放 白色小哈 
    				  dfs(i+1);    //@@@@@注意，这里的前提是，第i行已经放好“黑色小哈和白色小哈了”，那么就跳到下一行去放 
    				  e[i][j3]=1;   //这里是回溯(递归回溯)，就是(i,j3)这个位置可以放白色小哈，
    				               //但是我想看看(i,j3+1)这个位置行不行,所以我先还原e[i][j3]这个位置 	              
     
    			  }
    		  }
    		
    		}
    
    		e[i][j2]=1;    //这里也是回溯，只是看看“白色小哈”回溯完了，再让“黑色小哈”回溯 
    	}
    }
    
    int ok(int x,int y){    //这个函数是判断这个位置能不能放小哈 
    
    	if(e[x][y]!=1)
    		return 0;   //e[x][y]!=1说明这个位置已经有小哈或者这个位置是e[x][y]=0不能放 
    
    	int i,j;
    	int sign_2=0,sign_3=0;
    	for(i=1;i<=n;i++){
    		for(j=1;j<=n;j++){
    
    			if(e[i][y]==2||e[x][j]==2)   //这是看看(x,y)这个位置同一列或同一行有没有“黑色小哈” ，2代表黑色小哈 
    				sign_2=1;//有就标记 
    			
    //这是
    			if((i-j==x-y||i+j==x+y)&&e[i][j]==2)//看看(x,y)这个位置的对角线上有没有黑色小哈  
    				sign_2=1;//有就标记 
    		
    
    			if(e[i][y]==3||e[x][j]==3)//这是看看(x,y)这个位置同一列或同一行有没有“白色小哈” ，3代表白色小哈
    				sign_3=1;
    			
    
    			if((i-j==x-y||i+j==x+y)&&e[i][j]==3)//看看(x,y)这个位置的对角线上有没有白色小哈
    				sign_3=1;
    		}
    	}
    
    	if(sign_2==0&&sign_3==0)  //如果以上情况都没有，也就是他可以放白色小哈和黑色小哈 
    		return 1;//返回1 
    
    	if(sign_2==0)  //如果上面的if语句没有执行 ，就来看看这里，表示可以放黑色小哈 
    		return 2;
    	if(sign_3==0)//如果上面的两条if语句没有执行 ，就来看看这里，表示可以放白色色小哈
    		return 3;
    
    	return 0;//如果上面的if语句  #都# 没有执行 就返回0，表示都不能放 
    }

0.0分

2 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

小哈哈

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

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

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

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

C语言训练-阶乘和数* （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题-题解(详细代码）---------典型的递归回溯

评论区

精彩推荐

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

矩形面积交（C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-字符串正反连接（C语言代码）

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

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

WU-输出正反三角形（C++代码）

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

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

小哈哈

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

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

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

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

C语言训练-阶乘和数* （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题-题解(详细代码）---------典型的递归回溯

评论区

精彩推荐

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

矩形面积交 （C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

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

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

WU-输出正反三角形 （C++代码）

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

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

C二级辅导-进制转换（C语言代码）

　　评论区

矩形面积交（C语言代码）

C语言训练-字符串正反连接（C语言代码）

WU-输出正反三角形（C++代码）