codeforces 377 A maze

2015年12月5日 0 作者 CrazyKK

http://codeforces.com/contest/377/problem/A
题意:给定一个n*m的maze. ‘.’代表空,‘#’代表墙。要求构造一种方案,使得将k个空格填成墙壁后不影响当前的连通性(即没有被填充的空格之间可以相互到达)
思路:一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。

但其实只要是可能在某条路径上的点,就都不一定可以变成墙。。而四个角显然可以被某条路径经过。

正确的解法很巧妙。以任意一个空格开始跑一遍dfs,设空格一共有sum个,那么就dfs到(sum-k)个。可以做好标记。通过dfs得到的这(sum-k)之间一定是联通的。那么只要填充剩下的就可以了。