1679--【USACO】Circus Tickets

1679: 【USACO】Circus Tickets


时间限制: 1.000 Sec  内存限制: 64 MB
提交: 16  解决: 0
[提交] [状态] [报告] [命题人:]

题目描述

Farmer John is taking 16 cows to see the three ring circus. Being cows, they are seated in the cow section, a 4x4 set of seats near the front of the audience. The seats, rows, and columns are numbered thusly:
     col 1    col 3
        | col 2 | col 4
        |   |   |   |
        1   2   3   4  <-- row 1
        5   6   7   8  <-- row 2
        9  10  11  12  <-- row 3
       13  14  15  16  <-- row 4
The cows are herded helter-skelter into the seats. It is only after they are seated that they check their tickets. In a revelation that will surprise no one, they are not necessarily in the proper seats. The layout of the cow seating is such that they can rearrange themselves only by rotating a row right or left or rotating a column up or down. The examples below show all four operations applied to the first row or column of the proper seating shown above:
  4   1   2   3     2   3   4   1     5   2   3   4    13   2   3   4
  5   6   7   8     5   6   7   8     9   6   7   8     1   6   7   8
  9  10  11  12     9  10  11  12    13  10  11  12     5  10  11  12
 13  14  15  16    13  14  15  16     1  14  15  16     9  14  15  16
Rot row 1 right    Rot row 1 left     Rot col 1 up      Rot col 1 down
Given the actual seating arrangement of the cows, determine a very good set of rotations to rearrange cows so that their tickets and seat numbers match. At least one solution always exists. Your score for each test case will depend on how close you get to the best number of rotations submitted by other contestants for that case. Your output sequence must be shorter than 500 operations in order to receive credit for this problem. Hint: The sequence 1l 1l 1l 4u 1r 4d 1l 1l 4u 1r 4u 4u 4u swaps the cow in the upper left seat with the cow to her right.

输入

Four lines, each with four space separated integers. Line 1 is the first row; line 2 is the second row; and so on.

输出

A series of output lines that contain the ordered sequence of rotations that will arrange the cows. Each line contains a row or column number (1..4) followed by a space followed by a lower-case letter that indicates the operation to be performed: 'r' for rotate a row right, 'l' for rotate a row left, 'u' for rotate a column up, and 'd' for rotate a column down.

样例

输入  复制
4 1 2 3 6 7 8 5 10 11 12 9 14 15 16 13
输出  复制
1 l 2 r 3 r 4 r

提示

ABOUT SAMPLE OUTPUT: [Other correct sequences are equally valid though might not garner as many points.]

来源/分类