编程介的小学生 2017-04-04 14:17 采纳率: 20.5%
浏览 717
已采纳

ICPC: Intelligent Congruent Partition of Chocolate

The twins named Tatsuya and Kazuya love chocolate. They have found a bar of their favorite chocolate in a very strange shape. The chocolate bar looks to have been eaten partially by Mam. They, of course, claim to eat it and then will cut it into two pieces for their portions. Since they want to be sure that the chocolate bar is fairly divided, they demand that the shapes of the two pieces are congruent and that each piece is connected.

The chocolate bar consists of many square shaped blocks of chocolate connected to the adjacent square blocks of chocolate at their edges. The whole chocolate bar is also connected.

Cutting the chocolate bar along with some edges of square blocks, you should help them to divide it into two congruent and connected pieces of chocolate. That is, one piece fits into the other after it is rotated, turned over and moved properly.

Figure F-1: A partially eaten chocolate bar with 18 square blocks of chocolate
For example, there is a partially eaten chocolate bar with 18 square blocks of chocolate as depicted in Figure F-1. Cutting it along with some edges of square blocks, you get two pieces of chocolate with 9 square blocks each as depicted in Figure F-2.

Figure F-2: Partitioning of the chocolate bar in Figure F-1
You get two congruent and connected pieces as the result. One of them consists of 9 square blocks hatched with horizontal lines and the other with vertical lines. Rotated clockwise with a right angle and turned over on a horizontal line, the upper piece exactly fits into the lower piece.

Figure F-3: A shape that cannot be partitioned into two congruent and connected pieces
Two square blocks touching only at their corners are regarded as they are not connected to each other. Figure F-3 is an example shape that cannot be partitioned into two congruent and connected pieces. Note that, without the connectivity requirement, this shape can be partitioned into two congruent pieces with three squares (Figure F-4).

Figure F-4: Two congruent but disconnected pieces
Your job is to write a program that judges whether a given bar of chocolate can be partitioned into such two congruent and connected pieces or not.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows.

w h
r(1, 1) ... r(1, w)
r(2, 1) ... r(2, w)
...
r(h, 1) ... r(h, w)
The integers w and h are the width and the height of a chocolate bar, respectively. You may assume 2 ≤ w ≤ 10 and 2 ≤ h ≤ 10. Each of the following h lines consists of w digits delimited by a space. The digit r(i, j) represents the existence of a square block of chocolate at the position (i, j) as follows.

'0': There is no chocolate (i.e., already eaten).
'1': There is a square block of chocolate.
You can assume that there are at most 36 square blocks of chocolate in the bar, i.e., the number of digit '1's representing square blocks of chocolate is at most 36 in each dataset. You can also assume that there is at least one square block of chocolate in each row and each column.

You can assume that the chocolate bar is connected. Since Mam does not eat chocolate bars making holes in them, you can assume that there is no dataset that represents a bar in a shape with hole(s) as depicted in Figure F-5.

Figure F-5: A partially eaten chocolate bar with a hole (You can assume that there is no dataset like this example)
Output

For each dataset, output a line containing one of two uppercase character strings "YES" or "NO". "YES" means the chocolate bar indicated by the dataset can be partitioned into two congruent and connected pieces, and "NO" means it cannot be partitioned into such two pieces. No other characters should be on the output line.

Sample Input

2 2
1 1
1 1
3 3
0 1 0
1 1 0
1 1 1
4 6
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 0
0 1 1 0
1 1 1 0
7 5
0 0 1 0 0 1 1
0 1 1 1 1 1 0
0 1 1 1 1 1 0
1 1 1 1 1 1 0
1 0 0 0 1 1 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
7 6
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
10 10
0 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
0 0
Output for the Sample Input

YES
NO
YES
YES
YES
NO
NO
YES

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-17 15:48
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名