编程介的小学生 2019-01-06 00:54 采纳率: 20.5%
浏览 280
已采纳

数据结构采用邻接表算法实现KAMI问题,怎么实现的,采用的C语言

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 2019-11-30 23:42
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 Matlab编程问题
  • ¥15 训练的多模态特征融合模型准确度很低怎么办
  • ¥15 kylin启动报错log4j类冲突
  • ¥15 超声波模块测距控制点灯,灯的闪烁很不稳定,经过调试发现测的距离偏大
  • ¥15 import arcpy出现importing _arcgisscripting 找不到相关程序
  • ¥15 onvif+openssl,vs2022编译openssl64
  • ¥15 iOS 自定义输入法-第三方输入法
  • ¥15 很想要一个很好的答案或提示
  • ¥15 扫描项目中发现AndroidOS.Agent、Android/SmsThief.LI!tr
  • ¥15 怀疑手机被监控,请问怎么解决和防止