所以，preparing自己下一个ieextreme比赛，我经历了一些过去problems.I发现一个真正困扰我，因为我想不出什么做，我大概可以使用一些暴力破解它使300线code，但我认为这不是什么人应该做这样的比赛，所以我需要你的帮助！

So,preparing myself for the next ieextreme competition I was going through some past problems.I found one that really troubles me,since I can't figure out what to do.I could probably make it using some bruteforce 300 lines code,but I think that this is not what someone is supposed to do in such competitions,so I need your help!!

位图检测形状

问题陈述：在图像分析中，通常要分析的位图，并观察形状present在它。对于这个问题，设计一个算法，以检测形状在给定的位图。形状present在地图上应从套正方形，长方形，三角形和平行四边形。

Problem statement: In image analysis, it is common to analyze a bitmap and observe the shapes present in it. For this problem, design an algorithm to detect shapes in a given bitmap. The shapes present in the map shall be from the set Square, Rectangle, Triangle and Parallelogram.

在位图中每个像素重新psented为位$ P $，1 - 再presenting黑色和0 - 再presenting白色。与会者预计将检测黑边的形状。输入第一行包含在重新psented为（行，列）$ P $像素位映像的大小。

In the bitmap each pixel is represented as a bit, 1 - representing black and 0 - representing white. Participants are expected to detect the shapes outlined in black. Input The first line will contain the size of the bit map in pixels represented as (Row,Column).

例如。 6,8。这意味着6行和8列的位图。下一行包含了一系列的十进制数字，从0到255之间用空格隔开。每个数字将重新present 8个二进制位的集合中的位图。 IE浏览器。 55重新presents二进制码型00110111。

E.g. 6,8 this means a bit map of 6 rows and 8 columns. The next line will contain a series of decimal digits from 0 to 255 separated by spaces. Each digit will represent a collection of 8 binary bits in the bitmap. IE. 55 represents a binary pattern 00110111.

注：可以有位图中的多种形状和NO的形状应相交。然而可以有形状嵌套彼此无任何交叉点。

Note: There can be multiple shapes in a bitmap and NO shapes shall intersect. However there can be shapes nested with each other without any intersection.

输出形状present在自己的名字，用逗号和空格分隔的升序位图。例如。长方形，正方形，三角形

Output The shapes present in the bitmap in ascending order of their names, separated by a comma and a space. Eg. Rectangle, Square, Triangle

注：目前在输出的末尾没有换行或空间，如果任何形状重复，则输出应包含尽可能多的重复的位图。 IE浏览器。如果有2个正方形和一个三角形，输出应为方形，方形，三角形

Note: There is NO linefeed or space at the end of the output If any shape repeats, the output should contain as many repetitions as in the bitmap. ie. If there are 2 squares and one triangle, the output shall be Square, Square, Triangle

实例设置1

输入：

6月8日

0 126 66 66 126 0

0 126 66 66 126 0

输出：矩形

实例设置2

输入：

6月16日

0 0 120 120 72 144 73 32 123 192 0 0

0 0 120 120 72 144 73 32 123 192 0 0

输出：平行四边形，广场

Output: Parallelogram, Square

我写了这个code，这样我可以想像的位图，并有2个列表（位图的行列数）...

I have written this code so that I can visualize the bitmap and have 2 lists(bitmap in rows and cols)...

rows,cols=(int(i) for i in raw_input().split())
nums=[int(n) for n in raw_input().split()]
mr=[]
for i in range(0,len(nums),cols/8):
    row=''
    for j in range(i,i+cols/8):
        b=bin(nums[j])[2:]
        b='0'*(8-len(b))+b
        row+=b
    mr.append(row)
mc=[''.join([mr[i][j] for i in range(rows)]) for j in range(cols)]

感谢您的时间......如果你能在Python，C ++或Ruby请回答，因为这些语言我可以理解，甚至算法...

Thank you for your time...Please answer if you can in Python,C++ or Ruby,since these are the languages I can understand or even algorithmically...

推荐答案

我的做法是这样的：

3箱子： Find the first black pixel (either leftmost-topmost, or topmost-leftmost). Trace the black path right and down (that is, loop until you hit a white pixel).

3 cases: 在该路径具有相同的长度：方形或三角形。检查BOTTOMLEFT像素的像素有权决定（黑色：方形，白色：三角形）。 在该路径有不同的长度：（？还是应该永远是45度），矩形或三角形。检查BOTTOMLEFT像素的像素有权决定（黑色：长方形，白色：三角形）。 路径之一不存在：三角形或平行四边形。假设该路径下的没有的存在：检查BOTTOMLEFT像素的像素有权决定（黑色：三角形，白色：平行四边形）。 The paths have same length: square or triangle. Check the pixel right of the bottomleft pixel to decide (black: square, white: triangle). The paths have different length: rectangle or triangle (? or should they always be 45 degrees?). Check the pixel right of the bottomleft pixel to decide (black: rectangle, white: triangle). One of the paths does not exist: triangle or parallelogram. Assuming the path down did exist: check the pixel right of the bottomleft pixel to decide (black: triangle, white: parallelogram).

删除形状和重复。

您检查每一个像素的时候（不是很确定有关常数）只是一个常数，所以这应该及时线在像素数上运行。

You examine every pixel only a constant number of times (not quite sure about that constant), so this should run in time linear in the number of pixels.