蓝桥杯算法提高VIP-棋盘多项式

题目

题目链接

题解

DFS。

整体思路：
横向分块，如下：

我们只需要按连通块的序号去深搜即可，对于每个连通块，我们可以选择其中的任何一个空格作为放“車”的位置，或者选择不在这个连通块中放“車”。因此，我们的问题转化为在dfs中如何确定连通块，如何确定连通块中的哪个格子可以放，哪个格子不能放。

解决连通块的确定，只需要解决左端点和右端点的确定即可，那么我们不妨去遍历这一行，遇到洞就说明分开了两个连通块（不严谨的说）。对于确定好的一个连通块，我们对这个连通块中的空格再进行遍历，这次遍历的目的是为了确定连通块中的一个空格作为这个要选择的位置，将选中的位置进行标记，再就可以进行深搜下一个连通块了，同时不能忘记不选的情况，此时不需要对记录已放“車”数量的变量进行++。

为了方便连通块的查找，我直接将dfs函数的第一个参数设置为行号，第二个参数设置为列号，这个列号对应的位置的左侧一定是一个洞，也就是说这个列号对应着一个连通块的左端点，从这个列向右侧遍历，遇到洞就说明这个连通块的右端点也确定了，就可以进行选择空格放“車”了。

我们进行标记的用处在于，每次要确定一个连通块中的空格能不能选时，需要向上面已经搜完的行去遍历。我就看看我如果选这个位置的空格，那么它上面会不会已经有“車”了，其实有“車”也不要紧，先遇到洞也可以隔开俩“車”的攻击。通过从当前列向列号小的列遍历，看是不是满足条件，满足条件才能选中当前这个位置的空格。

注意如何变行。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n, ans, bound, sum, mp[N][N], vis[N][N];

bool check(int row, int col) {
	int i = row-1; // 从上一行查起 
	for(;i >= 0;i --) {
		if(vis[i][col]) break; // 如果遇到車了，就跳出 
		if(!mp[i][col]) {i = -1; break;} // 如果遇到洞了，说明没有車在攻击范围内，i=-1是为了统一返回的条件表达式 
	}
	return  i < 0;
}

void dfs(int row, int col) { // 洞右侧紧邻的一个空格 
	if(sum >= bound) {ans++; return ;}
	if(col >= n) row ++, col = 0; // 变行操作 
	if(row >= n) return ;
	
	int i = col;
	for(;i < n;i ++) if(!mp[row][i]) break; // 找到洞了 
	
	sum ++;  // 选了，所以加一 
	for(int j = col;j < i;j ++) {
		if(check(row, j)) { // 检查，满足当前这一行上面没有車在攻击范围内，就可以dfs 
			vis[row][j] = 1; // 标记 
			dfs(row, i+1); // i+1为下一个连通块的左端点（当然也可能还是洞，但是没有影响） 
			vis[row][j] = 0; // 回溯 
		}
	}
	sum --; // 回溯，下面进行不选操作 
	
	dfs(row, i+1); // 此连通块内的空格，都不选 
}

int main()
{
	cin>>n;
	for(int i = 0;i < n;i ++)
	for(int j = 0;j < n;j ++)
	cin>>mp[i][j];
	
	for(int i = 1;i <= n*n;i ++) {
		
		memset(vis, 0, sizeof vis);
		ans = sum = 0;
		bound = i;
		
		dfs(0, 0);
		
		if(ans == 0) break;
		cout << ans << endl;
	}
	
	return 0;
}