The square chest

Sophia pressed the button in front of her, slamming her fist against it. The door rumbled and appeared to do nothing.

“Oh man, that’s not very interesting at all.” Sofia complained.

Suddenly, the the door hissed and a jet of ice cold steam billowed out. The door began moving out the wall as if it were pushed from the inside. Sofia and the other two stepped back, watching their feet. The wall finally stopped moving and revealed itself to be a large chest of some sort.

“Oh man, could it be treasure?” Sofia studied the chest intently.

Nikola poked his head through the doorway where the chest had just exited. “Well, there’s nothing in there but darkness.” He turned to the chest which stood several feet taller than him and began studying it himself. He noticed some carvings on the side. “Hey, this looks like a manifest of some sort. Or a contents label. Look, there Ag, Na, Li, Mg... all raw materials we could use to fabricate the parts we need to fix the ship!”

“There’s a keypad on it though... It’s locked.” Sofia said with a frustrated sigh.

“No problem, we can solve it. Let’s take a look!”

On the chest keypad is a grid of numbered dots. The grid is comprised of a square shaped array of dots and contains lines that connect some pairs of adjacent dots. The answer to the code is the number of squares that are formed by these lines. For example, in the figure shown below, there are 3 squares: 2 small squares and 1 medium square.

The dots are marked by the numbers 1 through 16. The endpoints of the lines are represented by lists of two numbers.

Input: A list of lines as a list of list. Each list consists of the two integers.

Output: The quantity of squares formed as an integer.

原题链接: http://www.checkio.org/mission/the-square-chest/

题目大义: 计算正方形的个数

思路: 递归搜索; 实际上因为, 题目限定有16个点, 因此总的正方形个数为14个, 这个观察在处理图一中如[6,7,8,10,12,14,15,16]正方形, [7,8,10,11,12,14,15,16]非正方形时起到作用

 1 squares = [[1,2,5,6], [2,3,6,7], [3,4,7,8], [5,6,9,10], [6,7,10,11],[7,8,11,12],[9,10,13,14],[10,11,14,15],[11,12,15,16], 2                     [1,2,3,5,7,9,10,11], [2,3,4,6,8,10,11,12], [5,6,7,9,11,13,14,15],[6,7,8,10,12,14,15,16], 3                     [1,2,3,4,5,8,9,12,13,14,15,16]] 4  5 def line_joint(node, lines_list, square_nodes, square_lines, lines_node): 6     lines_node.append(node) 7  8     for each in lines_list: 9         if each not in square_lines and node in each:10             square_lines.append(each)11 12             adjnode = 013             if each[0] == node:14                 adjnode = each[1]15             else:16                 adjnode = each[0]17 18             if adjnode == square_lines[0][0]: #link to the first node19                 if len(square_lines) % 4 == 0: #may be a squre20                     sorted_lines_node = sorted(lines_node)21                     rep = False22                     for pre_square in square_nodes:23                         if pre_square == sorted_lines_node:24                             rep = True25                             break26 27                     if rep == False:28                         square_nodes.append(sorted_lines_node)29             else:30                 if adjnode not in lines_node: #not a cycle31                     line_joint(adjnode, lines_list, square_nodes, square_lines, lines_node)32 33             square_lines.pop()34 35     lines_node.pop()36 37 def checkio(lines_list):38     """Return the quantity of squares"""39     square_lines = []40     lines_node = []41     square_nodes = []42 43     for i in range(0, 17):44         line_joint(i, lines_list, square_nodes, square_lines, lines_node)45 46     square_count = 047     for maybe_square in square_nodes:48         for formal_square in squares:49             if maybe_square == formal_square:50                 square_count += 151                 break52 53     return square_count

代码思路, 首先递归枚举出, 环形及边数是4的倍数的闭合图形, 最后通过事先存储好的正方形数字, 去匹配闭合图形, 得到图中的正方形数