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编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

拾犬回荒

为啥提交了还是错的，只对了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的其他文章

你可能喜欢

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

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

交换Easy （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

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

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

评论区

精彩推荐

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

时间转换（Java代码）

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

The 3n + 1 problem （C语言代码）

1128题解（返回值为数组的情况）

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

The 3n + 1 problem （C语言代码）

一元一次方程（C语言代码）

矩阵的对角线之和（C语言代码）

生日日数（C语言代码）

JakeLin

TA的其他文章

你可能喜欢

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

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

交换Easy （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

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

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

评论区

精彩推荐

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

时间转换 （Java代码）

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

The 3n + 1 problem （C语言代码）

1128题解（返回值为数组的情况）

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

The 3n + 1 problem （C语言代码）

一元一次方程 （C语言代码）

矩阵的对角线之和 （C语言代码）

生日日数 （C语言代码）

　　评论区

时间转换（Java代码）

一元一次方程（C语言代码）

矩阵的对角线之和（C语言代码）

生日日数（C语言代码）