编程介的小学生 2016-12-19 14:38 采纳率: 20.5%
浏览 961
已采纳

Cover

Description

Given an N * N matrix A, whose elements are positive integers and not larger than 10000. There are also some '*'s in matrix A. Your program must find such three (perhaps overlapping) rectangles that they would contain all the '*'s which are in matrix A and the areas of these three rectangles (the area of one rectangle define as the number of elements it covers) must be non-negative and not exceed a given integer M.

If several solutions exist, the program should find a solution with minimal total costs of these three rectangles. The cost of one rectangle defines as the sum of all the numbers it contains in matrix A.
Input

The first line of the input is an integer X representing the number of test cases. The following X blocks each represents a test case.

The first line of each block contains two numbers N and M (1 <= N <= 30, 0 <= M <= N * N) representing the size of the matrix and the maximum area of each rectangle. The second line contains a number C (0 <= C <= N * N), representing the number of '*'s in matrix A. The following C lines each contains two numbers X and Y (1 <= X, Y <= N), representing A[X]Ycontains a '*'. The following N lines each contains N numbers, representing the matrix A.
Output

For each block output one line, which contains an integer representing the minimum total costs, or 'Impossible' (without quote) if no solution exists.
Sample Input

5
1 1
0
9
1 1
1
1 1
9
5 6
5
1 1
3 4
4 3
4 5
5 4
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1
5 3
5
1 1
3 4
4 3
4 5
5 4
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1
5 2
4
1 1
3 4
4 3
4 5
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1
Sample Output

0
9
20
23
Impossible

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-19 15:48
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致
  • ¥15 禅道二次开发编辑版本,上传不了发行包