【2021CCPC河南省赛】欢度佳节

• 博客主页: https://blog.csdn.net/qq_50285142
• 欢迎点赞收藏✨关注❤留言  如有错误，敬请指正
• 虽然生活很难，但我们也要一直走下去

调bug调了一下午，终于调通了，真是太不容易了，以此发现自己对dfs的理解并不是很深刻，递归时某些逻辑出错（统计连通块的个数时），导致bug一时没有调出来

思路：
可以发现一共只有17个块，我们可以把所有块的情况列举出来，一共才 2 17 = 131072 2^{17}=131072 217=131072种情况，然后再乘上17时间复杂度完全满足。所以本题就是枚举所有情况（把每个块看成01两种状态，1代表可以走，0代表不可以走），然后暴力搜索，判断所有的块是否连通
v i s [ i ] [ j ] vis[i][j] vis[i][j]表示点 ( i , j ) (i,j) (i,j)的状态
s t [ i ] [ j ] st[i][j] st[i][j]表示点 ( i , j ) (i,j) (i,j)之前是否访问过
node中记录的是有效的点的坐标，即之前是否访问的点
cat为连通块的个数
ans为所有状态为1的块消除后所需要的的掷骰子的次数
cnt为状态为1的块的个数

本题求连通块的数目容易出错（也许是我菜吧）用一个cat记录即可，当每次访问到可以访问的块时，就对cat加一

#include
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
const int N = 1e5+5;
typedef pairpii;
vectornode;
int g[6][6];
bool vis[6][6],st[6][6];
int res,cnt,ans,cat;

void dfs(int i,int j)
{
	if(!vis[i][j]) return ;
	st[i][j] = true;
	bool is = true;
	for(int k=0;k<4;k++)
	{
		int nx = i + dx[k];
		int ny = j + dy[k];
		if(nx<1 or nx>5 or ny<1 or ny>5) continue;
		if(vis[nx][ny] && !st[nx][ny]) 
		{
			cat += 1;
			is = false;
			st[nx][ny] = true;
			dfs(nx,ny);
		}
	}
}
void solve()
{
	int all;
	res = 0;
	cin>>g[1][1]>>g[1][2]>>g[1][4]>>g[1][5];
	cin>>g[2][2]>>g[2][3]>>g[2][4];
	cin>>g[3][2]>>g[3][3]>>g[3][4];
	cin>>g[4][2]>>g[4][3]>>g[4][4];
	cin>>g[5][1]>>g[5][2]>>g[5][4]>>g[5][5];
	cin>>all;
	for(int i=0;i<(1<<17);i++)
	{
		cnt = 0,ans = 0,cat = 0;
		memset(vis,false,sizeof vis);
		memset(st,false,sizeof st);
		for(int j=0;j<17;j++)
		{
			if((i>>j)&1) 
			{
				vis[node[j].fi][node[j].se] = true,cnt++;
				ans += (g[node[j].fi][node[j].se]+5)/6;
			}
		}
		if(vis[5][1]) cat = 1;
		dfs(5,1);
		if(cat==cnt and ans<=all)	
			res = max(res,cnt);
	}
	cout<>_;
	while(_--)
	{
		solve();
	}
	return 0;
}

• C++ STL详解，超全总结(快速入门STL)
• 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）
• 区间贡献问题习题详解