TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2284
  • 题目
  • P2284【L1 SOLO 第九场 HN11 day1】贪吃蛇
    限制 : 时间限制 : 75000 MS   空间限制 : 65536 KB
    问题描述

    一些蛇覆盖了一个网格。每个格子要么是一个障碍物,要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接),且至少占据两个格子。蛇与蛇之间不重叠,蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个:
    1. 两个端点所在的格子在网格的边界。
    2. 蛇构成一个环,即两个端点相邻(垂直或水平,不能斜着),至少要占据4个格子(否则没法形成环)。
    给定一个网格,用𝑟×𝑐的字符矩阵描述:’#’代表障碍物,’.’代表空地。在满足前面所述的条件下覆盖所有空地,并使得端点在网格边界(即不构成环)的蛇尽量少。
    例如,以下网格:

    ......
    .#.##.
    .#....
    ....#.
    .##.#.
    ......
    


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

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

    输入格式

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

    输出格式

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

    样例输入

    ......
    .#.##.
    .#....
    ....#.
    .##.#.
    ......

    样例输出

    2