#BZOJ2379. Tc2008 Championship Snake蛇
-
ID: 824
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Tc2008 Championship Snake蛇
No submission language available for this problem.
题目描述
一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线（拐角处只能水平和竖直连接），且至少占据两个格子。蛇与蛇之间不重叠，蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个：
1. 两个端点所在的格子在网格的边界。
2. 蛇构成一个环，即两个端点相邻（垂直或水平，不能斜着），至少要占据4个格子（否则没法形成环）。
给定一个网格，用的字符矩阵描述：’#’代表障碍物，’.’代表空地。在满足前面所述的条件下覆盖所有空地，并使得端点在网格边界（即不构成环）的蛇尽量少。
例如，以下网格：
......
.#.##.
.#....
....#.
.##.#.
......
可以由下面三种方案覆盖。还有其它的方案，但是没有仅用一条不构成环的蛇就覆盖整个网格的方案。
给定一个网格的描述，输出最少需要多少条不构成环的蛇来覆盖这个网格。如果不存在能够覆盖网格的方案，输出-1。
输入格式
一个字符矩阵，行数和列数不超过12。输入文件中没有多余的空白字符，每行之后都有换行符。
输出格式
输出满足题目要求的那个整数。
......
.#.##.
.#....
....#.
.##.#.
......
2