洛谷P1524 十字绣 dfs+思维

前言

最近打算考研去软院，顺便向xmd了解了一点算法岗实习的行情，决定重拾算法能力，多多刷题。

现在在刷洛谷的题单和vijos的训练计划，听很多同学说leetcode很不错，打算把vj的训练计划刷完后看看，然后再去做做Atcoder和CF。

---

题目描述

题目链接：洛谷P1524.

大意是：有一个 n × m n\times m n×m个网格的图，每个网格里的值表示这个网格的状态：

• \ ：左上角顶点到右下角顶点有一段线。
• / ：右上角顶点到左下角顶点有一段线。
• X：左上到右下有一段线，右上到左下也有一段线。
• . ：没有线。

其中，每段线只能从单位网格的一个顶点覆盖到其对角线，而一针中连续的两段线必须处在不同的面。

现在给出这个网格正面和背面两面的状态，问最少几针才能绣出来。

---

题目分析

我们考虑一个点 x x x：

它若存在一段正面的线和一段背面的线，那么我们就可以把这两条线同时删去。最后剩下的线，每条都一定是以 x x x为起点（或终点）的 1 1 1针。

设点 x x x最后剩下的线为 d e p ( x ) dep(x) dep(x)，那么我们只需要找出与 x x x相连的（不论是正面还是背面）所有点的 d e p ( v ) dep(v) dep(v)之和，最后将这个和除以 2 2 2就是这个联通块所需要的针数了。然后遍历整张图，把所有的连通块都计算一遍即可。

特判一种情况：若一个连通块的 ∑ d e p ( v ) = 0 \sum dep(v)=0 ∑dep(v)=0，其实这个连通块也需要 1 1 1针。（例如一个单位网格的对角线两点，在正面和背面同时有一段线）

---

示例代码

#include
using namespace std;

const int maxn = 45000;

int n, m, Ans;
int d[maxn][2], vis[maxn];
int cnt, bg[maxn], nxt[maxn<<3], to[maxn<<3]; //数组大小一定要开够

int bh(int x, int y){ //离散化 x行y列的点对应的编号
	return (x-1)*m + y;
}

void add(int x, int y, int z){ //建图
	to[++cnt] = y;
	nxt[cnt] = bg[x];
	bg[x] = cnt;
	++ d[x][z];
	
	to[++cnt] = x;
	nxt[cnt] = bg[y];
	bg[y] = cnt;
	++ d[y][z];
}

int dfs(int x){ //找联通块，并计算联通块的贡献
	vis[x] = 1;
	
	int back = abs(d[x][0] - d[x][1]);
	for(int e=bg[x]; e; e=nxt[e]){
		int t = to[e];
		if(!vis[t])
			back += dfs(t);
	}
	
	return back;
}

int main(){
	char c, s[205], laji[10];
	
	scanf("%d%d", &n, &m);		gets(laji); //处理行末回车
	++ n;	++ m; // 一共(n+1)*(m+1)个点
	for(int k=0; k<2; ++k)
		for(int i=1; i<n; ++i){
			gets(s);
			int l = strlen(s);
			for(int j=1; j<m; ++j){
				c = s[j-1];
				int bh1, bh2, bh3, bh4;
				if(c == '\'){
					bh1=bh(i,j), bh2=bh(i+1,j+1);
					add(bh1, bh2, k);
				}
				else if(c == '/'){
					bh1=bh(i,j+1), bh2=bh(i+1,j);
					add(bh1, bh2, k);
				}
				else if(c == 'X'){
					bh1=bh(i,j+1), bh2=bh(i+1,j), bh3=bh(i,j), bh4=bh(i+1,j+1);
					add(bh1, bh2, k);	add(bh3, bh4, k);
				}
			}
		}
	
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j){
			int bhx = bh(i,j);
			if(!vis[bhx] && bg[bhx]){ //遍历整张图，找所有联通块
				int s = dfs(bhx);
				if(!s)	Ans += 1; //特判
				else	Ans += s/2;
			}
		}
		
	printf("%d", Ans);
	return 0;
}

前向星的 n x t 、 t o nxt、to nxt、to数组一定要算清楚大小啊啊啊啊啊啊！一开始开成maxn × 4 \times 4 ×4一直RE，后来意识到背面也有边才发现要maxn × 8 \times 8 ×8.

---

后记

一开始想的是把一个顶点的正面和背面看成两个点，正面的一段线就给正面的两点连权值为 1 1 1的边，背面的就给背面的两点连权值为 1 1 1的边。如果一个顶点在正面和背面都有边，那就给正面和背面的这两点连一条权值为 0 0 0的边。

这个做法和正解思路基本一样，但是当时没想清楚问题的本质，一时没做出来。看来以后要先从问题最基础的情况思考起，这样更容易找到问题的本质。