BZOJ4213 - 贪吃蛇

BZOJ4213 - Click Here

  

Description

  最近lwher迷上了贪吃蛇游戏,在玩了几天却从未占满全地图的情况下,他不得不承认自己是一个弱菜,只能改去开发一款更弱的贪吃蛇游戏。

  在开发的过程中,lwher脑洞大开,搞了一个多条蛇的模式。但由于这种模式太难操作,于是他只好改变游戏的玩法,稍微变化一下游戏目标。

  新的游戏是这样的:

  一些蛇覆盖了一个网格。每个格子要么是一个障碍物,要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接),且只是占据两个格子。蛇与蛇之间不能重叠,蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个:

  1、两个端点所在的格子在网格的边界。

  2、蛇构成一个环,即两个端点相邻(垂直或水平,不能斜着),至少要占据4个格子(否则没法形成环)。

  给定一个网格,用r x c的字符矩阵描述:‘#’代表障碍物,‘.’代表空地。在满足前面所述的条件下覆盖所有空地,并使得端点在网格边界(即不构成环)的蛇尽量。(如果一条蛇既构成环,又是端点在边界,那么不计入答案)

  例如,以下网格:

  可以由下面三种方案覆盖。还有其他的方案,但是没法仅用一条不构成环的蛇就覆盖整个网络的方案。

  给定一个网络的描述,输出最少需要多少条不构成环的蛇来覆盖这个网格。如果不存在能够覆盖网格的方案,输出-1。

  

Input

  一个字符矩阵,行数和列数不超过12。输入文件中没有多余的空白字符,每行之后都有换行符。

  

Output

  输出满足题目要求的那个整数。

  

Solutions

  将网格看做点,网格之间的交线看做是边。

  那么一个环需要满足环上所有点度数为$2$;边界上的一条蛇,则需要满足两个端点度数为$1$,其余端点度数为$2$。

  即现在转换成这样一个问题,可以在图内任意加边,并且满足边界上的点度数为$1$或$2$,其余点度数为$2$。

  

  考虑如何解决此问题。

  对网格黑白染色。设黑色点集为$A$,白色点集为$B$,则每条边均为$A$与$B$的连边,而度数限制可以看做是一个取值区间。建图$S \to A \to B \to T$。判断是否存在答案,等价于判断该上下界网络流是否有解。

  

  考虑如何求最终答案。

  易知为使得最终答案尽可能小,需要度数为$2$的点尽量多。该限制等价于跑上下界最大流。

  因此对原图跑有源汇上下界最大流,最后统计度数为$1$的节点数即可。

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang