【FJ2015集训】贪吃蛇

2015年7月13日3,1246

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

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

新的游戏是这样的:

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

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

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

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

例如,以下网格:

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

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

【输入格式】

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

【输出格式】

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

题解

考场上写个随机起点贪心啥的得了70+分

善良的学长的题解

本题中,如果构成环,则二分染色后,蛇的头和尾异色,以此为突破点。

首先棋盘黑白染色,之后源向白色点流入2流量,黑色点向汇流出2流量。这2流量是强制的,也即需要上下界来限制。

同时,白色点可向相邻的点流出1流量。 这样,任何一个环形蛇,均被拆成了两段,一段是源-头-尾 另一段是源-头-躯干-尾

下面考虑另一种蛇

这里,另一种蛇可以被认为,在边界上,头部花费1的代价,取消掉1的流入流量,尾部花费1的代价,取消掉1的流出流量。

所以对于白色点,建一条到汇的,容量1,费用1的边。

对于黑色点,建一条从源点出发的,容量1,费用1的边。

此时求出最小费用可行流就能得出答案。

显然,如果无法满足下界流量,那么无解,输出-1。

不靠谱的乱搞

费用流

 

  • hjz2015年7月14日 上午10:16 回复

    请问学长这题有没有可以输出一组解的方法

    #1  
    • hzwer2015年7月14日 上午10:34 回复
      admin

      据说是TC上的原题,原题是要输出解的0.0我没考虑过

      #11
      • hjz2015年7月14日 上午10:44 回复

        刚才问了出题人 他说可以通过残量网络来求出

        #12
  • sherlock_zhuang2016年2月22日 下午6:29 回复

    黄学长讲的好,乱搞也写得好!

    #2  
  • 躺着打DOTA2016年2月25日 上午9:53 回复
    #3