2n皇后问题 [dfs][一个高效的优化]

2/10/2017来源:ASP.NET技巧人气:849

题目描述

给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。

现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法?

输入

输入的第一行为一个整数n,表示棋盘的大小。

接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。

n小于等于8。

输出

输出一个整数,表示总共有多少种放法。

样例输入

4 1111 1111 1111 1111 4 1011 1111 1111 1111 样例输出 2 0

解题报告

探讨2n皇后问题之前,先看看N皇后问题 用vis[3][] 标记已经访问过的纵,和两个对角线。这样复杂度就可以大大减低o(1)的时间内可以判定是否可行。

对于纵排是否可以访问只要记录那一纵的横坐标即可;对角线是直线,我们记录他的截距即可。

说了这么多,为什么我没提到横排的问题,这个自己体会代码吧,懒得打字了。

#include<stdio.h> #include<string.h> #define MAX_N 8 bool map[MAX_N][MAX_N]; bool vis[3][MAX_N*2]; int N,ans; void dfs_1(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]) continue; vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; } } int main() { while(~scanf("%d",&N)){ for(int j=0;j<N;j++) for(int k=0;k<N;k++) scanf("%1d",&map[k][j]); ans=0; dfs_1(0); PRintf("%d\n",ans); } return 0; }

在上面基础上dfs再走一遍就解决2n皇后问题了 //我把bool型的map写成char,因为这个WA了两次,,,我也不知道原因,理论上是没问题的,不知道是oj的问题还是数据的问题

#include<stdio.h> #include<string.h> #define MAX_N 20 char map[MAX_N][MAX_N]; bool vis[3][MAX_N*2]; bool vis_0[3][MAX_N*2]; bool used[MAX_N][MAX_N]; int N,ans; void dfs_0(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis_0[0][i]||vis_0[1][i+cnt]||vis_0[2][N-cnt+i]||used[cnt][i]||map[cnt][i]=='0') continue; vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=true; dfs_0(cnt+1); vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=false; } } void dfs_1(int cnt){ if(cnt==N){ dfs_0(0); return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]||map[cnt][i]=='0') continue; used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; } } int main() { while(~scanf("%d",&N)){ for(int j=0;j<N;j++) scanf("%s",map[j]); memset(vis,0,sizeof(vis)); memset(vis_0,0,sizeof(vis_0)); memset(used,0,sizeof(used)); ans=0; dfs_1(0); printf("%d\n",ans); } return 0; }