当前位置: 代码迷 >> 综合 >> JakeLin-[蓝桥杯]棋盘多项式-题解
  详细解决方案

JakeLin-[蓝桥杯]棋盘多项式-题解

热度:80   发布时间:2023-11-13 15:30:50.0

八皇后问题是在棋盘上放皇后,互相不攻击,求方案。变换一下棋子,还可以有八车问题,八马问题,八兵问题,八王问题,注意别念反。在这道题里,棋子换成车,同时棋盘也得  换,确切说,是进行一些改造。比如现在有一张n*n的棋盘,我们在一些格子上抠几个洞,这些洞自然不能放棋子了,会漏下去的。另外,一个车本来能攻击和它  的同行同列。现在,你想想,在攻击的过程中如果踩到一个洞,便会自取灭亡。故,车的攻击范围止于洞。 
此题,给你棋盘的规模n,以及挖洞情况,求放k个车的方案数(k从0到最多可放车数) 

数据规模和约定 
n< =8 

输入

第一行一个整数n表示棋盘大小 
接下来n行,每行n个用空格隔开的数字0或1,0的形状表示洞,1表示没有洞 

输出

若干行,第i行表示放i个车的方案数 

样例输入

3
1 0 1
1 1 1
1 0 1

样例输出

7
12
4

题目链接(可提交)

正如题目所说,本题是基于回溯法的经典题目:《n皇后问题》 提出的,在深入理解这道题目之前,强烈推荐先戳一下之前的文章,增强“n皇后问题”的理解  《N皇后和2N皇后问题的解析》


一、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)安全否 :

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算法过程,具体解析写在代码中:

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前的状态}}}
}

完整代码如下: 

#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;
}

若对你有所帮助,万分荣幸!