B - N皇后问题
2024-08-26 00:21:17
一天课下,张老板研究起了国际象棋,渴望完美的他更改了棋盘的大小,在N*N的方格棋盘放置了N个皇后,希望它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上)
张老板把这个艰巨的任务交给了你,对于给定的N,求出有多少种合法的放置方法。
张老板把这个艰巨的任务交给了你,对于给定的N,求出有多少种合法的放置方法。
Input共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。Output共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。Sample Input
1
8
5
0
Sample Output
1
92
10
第一次看到这个题感觉很难,后来通过看视频学会了一种递归算法来解这道问题,想明白后还是很有意思的,不过递归是一种很低效的算法,提交的时候TEL了,正确的解法应该是用回溯算法,以后有时间再理解
递归算法(低效)
#include<stdio.h>
#include<string.h> int count = ;
int t; int notDanger(int row, int j, int (*arr)[])
{
int flag1, flag2, flag3, flag4, flag5;
int i, k; flag1 = flag2 = flag3 = flag4 = flag5 = ; //判断列是不是危险
for( i = ; i < t; i++ )
{
if(arr[i][j] == )
{
flag1 = ;
break;
}
} //判断左上方
for( i = row, k = j; i >= && k >= ; i--, k-- )
{
if(arr[i][k] == )
{
flag2 = ;
break;
}
} //判断左下方
for( i = row, k = j; i < t && k >= ; i++, k-- )
{
if(arr[i][k] == )
{
flag3 = ;
break;
}
} //判断右上方
for( i = row, k = j; i >= && k < t; i--, k++ )
{
if(arr[i][k] == )
{
flag4 = ;
break;
}
} //判断右下方
for( i = row, k = j; i < t && k < t; i++, k++ )
{
if(arr[i][k] == )
{
flag5 = ;
break;
}
} if(flag1 == || flag2 == || flag3 == || flag4 == || flag5 == )
return ; else
return ;
} void nQueen(int row, int n, int (*arr)[])
{
int arr2[][], i, j; for( i = ; i < n; i++ )
{
for( j = ; j < n; j++ )
{
arr2[i][j] = arr[i][j];
}
} if(row == n)
count++; else
{
//该位置没有危险
for( j = ; j < n; j++ ) //这一部分代码其实往下会产生很大的容量
{ //有时候自己会在这部分,搞混。
if(notDanger(row, j, arr))
{
for( i = ; i < n; i++ )
{
arr2[row][i] = ;
} arr2[row][j] = ; nQueen(row+, n, arr2);
}
}
}
} int main()
{
int arr[][], i, j; while(scanf("%d", &t) != EOF && t)
{
count = ; for( i = ; i < t; i++ )
{
for( j = ; j < t; j++ )
{
arr[i][j] = ;
}
} nQueen(, t, arr);
if(count == )
printf("None\n");
else
printf("%d\n", count);
} return ;
}
回溯算法
#include<stdio.h>
#include<string.h> int n,tmp;
int map[]; void DFS(int k)
{
int i,j,flag;
if(k==n+)
{
tmp++;
return;
}
else
{
for(i=;i<=n;++i)
{
map[k]=i;
flag=;
for(j=;j<k;++j)
{
if(map[j]==i||i-k==map[j]-j||i+k==map[j]+j) // 注:1、i=map[k] 2、不在同一条斜线的两点的含义是行标到对角线的的距离不相等
{
flag=;
break;
}
}
if(flag)
DFS(k+);
}
}
} int main()
{
int i,m;
int ans[];
for(n=;n<=;++n)
{
tmp=;
DFS();
ans[n]=tmp;
}
while(scanf("%d",&m),m)
{
printf("%d\n",ans[m]);
}
return ;
}
最新文章
- DES算法
- 去掉tableview顶部留白
- linux 内核学习之五 system_call过程分析
- nyoj298_点的变换_错误
- iOS沙盒目录
- MySQL把多个字段合并成一条记录的方法
- 清空select内容
- JVM 类型的生命周期学习
- spring替代方法
- Codeforces Beta Round #85 (Div. 1 Only) A. Petya and Inequiations 贪心
- LRU与MRU算法
- Android(java)学习笔记215:多线程断点下载的原理(JavaSE实现)
- JAVA获取oracle中sequences的最后一个值
- 对话框(alert,prompt,confirm,showModalDialog)
- 小飞淙在博客上的第一天——NOIP201505转圈游戏
- Error when sending message to topic test with key: null, value: 2 bytes with error: (org.apache.kafka.clients.producer.internals.ErrorLoggingCallback)
- SpringBoot配置日志logback
- RabbitMQ基础知识及Linux安装
- socket通信的遇到的问题1
- html元素不可见的三种方式