编程介的小学生 2017-02-18 07:27 采纳率: 20.5%
浏览 918
已采纳

Robotic Jigsaw

Statement of the Problem
Your task here is to write a program to aid in the assembly of a jigsaw puzzle by a robot.

The puzzle is a rectangular array of flat four-sided pieces. Except for the outer borders, each side of each piece is shaped in such a way that it matches one side of exactly one other piece.

When the puzzle is presented to the robot, all the pieces are scrambled and spread out on a table, face up, in front of the robot's camera eye. Let's assume that someone already wrote some software that does the image processing part of the problem: find the puzzle pieces in the image captured by the camera, break the outline of each piece into its four sides, and find pairs of sides that have the same shape. Your task is to program the next step - namely, decide where in the grid each piece should be placed, and how it should be rotated.

The image-processing software assigns, to each piece that the robot sees on the table, a unique piece number between 0 and N-1, in some arbitrary order. It also labels the sides of the piece with integers 0, 1, 2, 3, in counterclockwise order, starting from an arbitrary side:

Input Format

The input contains several consecutive instances of the problem. Each instance consists of: one line containing two integers N, 0 < N < 500 (the number of pieces) and K; the come K lines, one for each pair of similar sides that were found among all pieces seen by the robot, in arbitrary order. Each of these lines contains four integers like this:

17 2 23 1

This line says that side number 2 of piece number 17 fits side 1 of piece 23. Therefore, in the assembled puzzle, pieces 17 and 23 should be neighbors, in one of these four positions:

You can assume that the input data includes enough information to assemble the puzzle completely. Note, however, that it may not include all pairs of matching sides, and it may include some redundant pairs that could be deduced from the previous ones. The end of the input is marked by a line containing a single 0.

Output Format

For the ith instance of the input file you should write the line Instance i:, followed by a sequence of N lines, one for each piece, containing four integers such as 6 9 17 2. This line says that piece number 17 should be placed in row 6 and column 9 of the grid, turned so that its side number 2 lies at the bottom. (By convention, rows are numbered from top to bottom, and columns from left to right, starting with 0.)

Note also that any solution can be turned by multiples of 90 degrees to give three other valid solutions. In order to make the output unique, your must turn your solution around so that piece number 0 has its side number 0 at the bottom (turned towards the robot). In any case, the upper left corner of the assembled puzzle should be at position [0, 0].

The lines of the output should be presented in lexicographic order of the rows and columns, as shown in the sample output.

Sample Input

12 13
0 0 5 0
0 2 6 2
1 2 11 0
1 3 9 2
2 0 5 1
2 1 4 2
3 0 10 3
3 3 8 0
4 0 7 1
4 1 11 1
6 1 7 2
8 2 9 3
10 0 11 2
0

Sample Output

Instance 1:
0 0 3 3
0 1 10 0
0 2 7 1
0 3 6 2
1 0 8 2
1 1 11 0
1 2 4 2
1 3 0 0
2 0 9 1
2 1 1 0
2 2 2 3
2 3 5 2

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-22 14:18
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常