Pro.ID22253 TitleThe Game of Tetris Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22253 AC0 Submit0 Ratio- 时间&空间限制描述
In this problem, you’re given an NxN grid of integers. We want to place a single piece of Tetris on the grid such that the sum of the numbers below the piece are the maximum. Notice that all but the last Tetris piece can be rotated by 90 degrees. Some pieces even have four different orientations. Any orientation is acceptable as long as the piece completely fits inside thegrid. For example, the left-most piece can be placed on the first row of the grid, with a sum of 80. It can also be placed, for example, on the third column, yielding a sum of 91. As a matter of fact, in a 4x4 grid, we can have 77 different ways to place the Tetris pieces. In the sample grid shown onthe right, the largest sum that can be achieved is 120. 输入Your program will be tested on one or more test cases. The first line of a test case has a single integer N denoting the grid size where 4 ≤ N ≤ 100. The grid will be specified using N lines starting on the second line in a row major format. Each line will have N integers separated by one or more spaces. The absolute value of each integer in the grid will not exceed 1, 000, 000. The end of the input cases is specified by a zero on a separate line. 输出Description
In this problem, you’re given an NxN grid of integers. We want to place a single piece of Tetris on the grid such that the sum of the numbers below the piece are the maximum. Notice that all but the last Tetris piece can be rotated by 90 degrees. Some pieces even have four different orientations. Any orientation is acceptable as long as the piece completely fits inside thegrid. For example, the left-most piece can be placed on the first row of the grid, with a sum of 80. It can also be placed, for example, on the third column, yielding a sum of 91. As a matter of fact, in a 4x4 grid, we can have 77 different ways to place the Tetris pieces. In the sample grid shown onthe right, the largest sum that can be achieved is 120. Input Your program will be tested on one or more test cases. The first line of a test case has a single integer N denoting the grid size where 4 ≤ N ≤ 100. The grid will be specified using N lines starting on the second line in a row major format. Each line will have N integers separated by one or more spaces. The absolute value of each integer in the grid will not exceed 1, 000, 000. The end of the input cases is specified by a zero on a separate line. Output For each test case, output the result on a single line using the following format: k. result Where k is the test case number (starting at 1,) and result is the largest sum that can be obtained. Sample Input 4 70 2 1 7 7 1 30 6 4 30 30 5 3 1 30 2 0 Sample Output 1. 120 Source 样例输入4 70 2 1 7 7 1 30 6 4 30 30 5 3 1 30 2 0 样例输出1. 120 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 18:53 , Processed in 0.035646 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
Tetris is a famous video game that has 5 pieces similar to these:
