UVA11694 Gokigen Naname题解

• 写在前面
• Solution
• Code

写在前面

UVA的题需要自己读入一个 \(T\) 组数据，别被样例给迷惑了

Solution

每个格子只有两种填法且 \(n \le 7\)，暴力搜索两种填法，开cnt数组统计连接个数。

填一个格子，如果是 "\"，格子左上角和右下角的 \(cnt++\)，如果是 "/"，格子左下角和右上角的 \(cnt++\)。只有更改后的 \(cnt\) 小于等于目标 \(cnt\)才继续向下搜，否则回溯

发现每填一个格子，连接格子左上角的格点的个数就可以被确定，那么只有左上角的格点个数等于目标格点个数或没有要求才继续搜索，否则回溯

如果搜索到第 \(n + 1\) 列时，要额外判断边界第 \(n + 1\) 列的 \(cnt\)是否满足对应的个数
如果搜索到第 \(n\) 行时，要额外判断边界第 \(n + 1\) 行的 \(cnt\) 是否满足对应个数

如何保证无环？不难想到，只有在填 "/" 时才有可能出现环，那么在填 "/" 之前，先判断是否有环

如何处理点的坐标？把行看做十位，把列看做个位就好啦

• 算法一：考虑可撤销并查集，然而我不会

• 算法二：发现n很小，每次判断时 \(n^2\) 扫一遍建图，在 \(dfs\) 看看能否从左下角跑到右上角

• 算法三：很显然算法二很傻逼，直接用并查集维护就好，加完边后判断左下角和右上角是否在同一并查集里，省去 \(dfs\) 的时间，注意清零！

最后输出方案就好啦

Code

我一开始建图跑的，后来也没改（因为懒

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<>(ch + 1);
			for(int j = 1; j <= n + 1; ++j){
				if(isdigit(ch[j])) go[i][j] = ch[j] - '0';
				else go[i][j] = 9;
			}
		}
		
		dfs(1, 1);
//		for(int i = 1; i <= n + 1; ++i){
//			for(int j = 1; j <= n + 1; ++j){
//				cout<