JakeLin

正如题目所说，本题是基于回溯法的经典题目：**《n皇后问题》** 提出的，在深入理解这道题目之前，希望可以可以先戳一下之前的文章，进行“n皇后问题”的理解 :tw-1f449: :tw-1f449:
> [N皇后和2N皇后问题的解析](https://blog.dotcpp.com/a/67157 "N皇后问题")

------------

##### 一、n皇后问题的思路简述
看到上述文章中的step变量了吗，它指的是第step个皇后的放入情况，同时也指第step行皇后的放置情况，因为：
##### n皇后问题只能放入n个皇后，并且是每行只有一个，每列也只有一个
当我们确定step时，遍历这一行的每一列去找寻符合条件的位置。

------------

##### 二、本题与n皇后问题有何不同
> 题目中：现在，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。 
举例：某行是 1 0 1

这一行的第1列若放下一车，第3列并不会被其攻击，因为车的攻击范围止于第2列的洞。
所以：
- 问：当我们知道点（i,j）被访问时，我们需要去哪找寻下一个位置**？**
**答: 没错，我们需要遍历（i,j）之后的所有点找寻符合条件的位置，同行同列也可哦**。
- 问：那么何为符合条件的位置**？**
**答:我们假设这个位置是（x,y）
在同一行上：如若（x，1~y）中有1，并且他们之间没有0阻挡，那么它变会被攻击，不是合法的位置，否则即使安全位置
在同一列上：如若（1~x，y）中有1，并且他们之间没有0阻挡，那么它变会被攻击，不是合法的位置，否则即使安全位置**

这里我们就写一个check( )，判断一下某一个点(x,y)安全否 :
```cpp
bool check(int x,int y,int n) {
	for(int i=x-1; i>=1; i--) {
		if(map[i][y]==0) break; //如果在遇到1之前遇到0，那么它是安全的 
		if(vis[i][y]==1) return false; //如果还没遇到0就遇到了1，那就它是危险的 
	}
	for(int i=y-1; i>=1; i--) {
		if(map[x][i]==0) break;
		if(vis[x][i]==1) return false;
	}
	return true;
}
```

------------

##### 三、如何实现
和n皇后问题一样，用DFS算法实现该过程，解释变量：

`dfs(int x,int y,int t,int n) // 访问了(x,y)；此时t个车；n为棋盘规模`
`int num[maxn] // num[i]表示i个车的方案数`

DFS算法过程，具体解析写在代码中：
```cpp
void dfs(int x,int y,int t,int n) {
	if(t<=n*n) num[t]++;
	for(int i=x; i<=n; i++) {  //遍历 (x,y)及其之后的所有点，从（1,1）开始
		int j;  // 遍历：x行y列之后的+下面所有行
		if(i==x) j=y;
		else j=1;
		for(;j<=n; j++) {
			if(vis[i][j]==0 && map[i][j]==1 && check(i,j,n)) { //满足条件的访问：没访问过 && 是陆地 && 不被攻击
				vis[i][j]=1;
				dfs(i,j,t+1,n);
				vis[i][j]=0;  // 回溯到DFS前的状态
			}
		}
	}
}
```

------------

完整代码：
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 10;
int map[maxn][maxn];
int vis[maxn][maxn];
int num[maxn];
bool check(int x,int y,int n) {
	for(int i=x-1; i>=1; i--) {
		if(map[i][y]==0) break; //如果在遇到1之前遇到0，那么它是安全的 
		if(vis[i][y]==1) return false; //如果还没遇到0就遇到了1，那就它是危险的 
	}
	for(int i=y-1; i>=1; i--) {
		if(map[x][i]==0) break;
		if(vis[x][i]==1) return false;
	}
	return true;
}
void dfs(int x,int y,int t,int n) {
	if(t<=n*n) num[t]++;
	for(int i=x; i<=n; i++) {
		int j;
		if(i==x) j=y;
		else j=1;
		for(;j<=n; j++) {
			if(vis[i][j]==0 && map[i][j]==1 && check(i,j,n)) {
				vis[i][j]=1;
				dfs(i,j,t+1,n);
				vis[i][j]=0;
			}
		}
	}

}
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin>>map[i][j];
		}
	}
	dfs(1,1,0,n);
	for(int i=1; i<=n*n;i++) {
		if(num[i]!=0) cout<<num[i]<<endl;
	}
	return 0;
}
```
或许对你有些帮助，加油，觉得有用请为我评个分吧:bowtie:

0.0分

34 人评分

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

　　评论区

拾犬回荒

为啥提交了还是错的，只对了18

2021-02-24 11:14:24

鼬殇

您太强了。。

2021-02-16 12:08:31

吱屋猪

写得太好了，豁然开朗。

2020-03-12 12:25:07

JakeLin

写题解真不易，多谢大家支持（抱拳）

2020-03-03 17:19:02

JakeLin

TA的其他文章

你可能喜欢

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

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

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

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

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

JakeLin-1540题-棋盘多项式-题解(C/C++代码)-详细解释/简单易懂/代码简洁

评论区

精彩推荐

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

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

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

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

核桃的数量（C语言代码）

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

循环入门练习5 （C语言代码）

蛇行矩阵（C语言代码）

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

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

JakeLin

TA的其他文章

你可能喜欢

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

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

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

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

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

JakeLin-1540题-棋盘多项式-题解(C/C++代码)-详细解释/简单易懂/代码简洁

评论区

精彩推荐

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

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

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

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

核桃的数量 （C语言代码）

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

循环入门练习5 （C语言代码）

蛇行矩阵 （C语言代码）

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

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

　　评论区

核桃的数量（C语言代码）

蛇行矩阵（C语言代码）