编程介的小学生 2017-08-29 01:22 采纳率: 20.5%
浏览 719
已采纳

KAMI

Problem Description
Little Bob found an interesting mobile game called KAMI in Google Play recently. In this game, you are given a 16*10 grid, and each cell is one of the 4 different colors.

The only thing you can do in this game is to choose a cell and a color, and then the entire 4-connected component, which contains the cell and has the same color as the cell, will be painted with the chosen color.

Your goal is to make all cells painted with the same color with the least painting steps. Also note that the optimal painting steps will be given, just the same as the original game.

For your convenience, we label the colors with integers 1..4. In the grid, we index the rows with integers 1..16 from top to bottom, and index the columns with integers 1..10 from left to right. Thus the cell in the i-th row and j-th column will be denoted by (i, j).

Once you choose to paint cell (7, 1) with orange color in the above picture, we will obtain:

Input
The first line contains an integer T (T<=5), which means there are T test cases in the input.

For each test case, the first line contains a positive integer n (n<=8), which denotes the optimal painting steps of this case. We ensure this is the least painting times to achieve the goal.

The next 16 lines in each test case describe the initial colors of each cell in the grid. Each line contains a string of length 10, which consists of digits '1'~'4'. For each test case, we ensure that the 4 colors all appear in the initial state.

Output
For each test case, output "Case #x:" (x means the case ID) in a separate line first. Then you should output exactly n lines. Each line contains three integers c, x, y (1<=c<=4, 1<=x<=16, 1<=y<=10), which means you choose to paint cell (x, y) with color c in this step.

If there exists more than one optimal solutions, you can output an arbitrary one.

Sample Input
2
3
4444444444
3332222333
3111111113
3332222313
3111111113
3132222333
3111111113
3332222313
3111111113
3132222333
3111111113
3332222313
3111111113
3132222333
3332222333
4444444444
5
1111213131
1111213131
4444243444
1111213131
4444444434
1111213131
2222222232
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131

Sample Output
Case #1:
2 14 2
3 15 7
4 12 8
Case #2:
4 4 5
4 16 9
2 5 10
1 7 10
3 16 10

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-12 16:40
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)