在一个10×10的方形图中,共有100个色块,每个色块是红橙黄绿蓝紫6种颜色之一,在这张图上有一个起点和一个终点。游戏开始后,起点每次可以改变为6种颜色之一,当起点改变后的颜色与相邻的色块颜色相同时,同种颜色会合并起来一起成为起点的一部分,最终经过不断改变颜色,起点与终点合并到一起就算胜利。在这个过程中,改变颜色的次数越少,游戏得分越高(步数相同的方案中,最终染色数量越多,得分越高)。
另外注意,在这个游戏中,起点和终点并不一定只有一块,相反,起点可能是相邻的很多块相同颜色,终点也可能是相邻的很多块相同颜色,且并不需要100个色块全部变为同一种颜色,只需要初始起点与终点的最终颜色一致即可。再次强调,起点每次改变颜色时都在扩张。
是否可以写一种算法,输入内容是10×10的100个颜色及起点终点的位置坐标,输出内容是最短路径及每次改变的颜色是什么? 一个例子,如下面的颜色板: matrix = [ ['红', '橙', '黄'], ['绿', '蓝', '紫'], ['绿', '橙', '黄'] ] 起点为[(0,0)]终点为[(2,2)] 第一步,起点改变为绿色,这样改变后,(0,0)(1,0)(2,0)都是起点的一部分了,如图: matrix = [ ['绿', '橙', '黄'], ['绿', '蓝', '紫'], ['绿', '橙', '黄'] ] 第二步,起点改变为橙色,这样改变后,(0,0)(0,1)(1,0)(2,0)(2,1)都变成了起点的一部分,如图: matrix = [ ['橙', '橙', '黄'], ['橙', '蓝', '紫'], ['橙', '橙', '黄'] ] 第三步,起点变为黄色,这样改变后,除了(1,1)(1,2)其他色块都是起点的一部分,如图: matrix = [ ['黄', '黄', '黄'], ['黄', '蓝', '紫'], ['黄', '黄', '黄'] ] 总共三步,游戏结束,因为第三步时,起点与终点变为了相同的颜色。
我自己用这个矩阵验证: game_board = [[1, 2, 6, 6, 6, 6, 6, 6, 6, 4], [1, 3, 6, 5, 6, 1, 2, 3, 6, 5], [3, 4, 6, 6, 1, 2, 3, 4, 6, 6], [4, 5, 6, 1, 2, 3, 4, 5, 6, 1], [5, 6, 1, 2, 3, 4, 5, 6, 6, 2], [6, 1, 2, 3, 4, 5, 6, 1, 6, 3], [1, 2, 3, 4, 5, 6, 1, 2, 6, 4], [2, 3, 4, 5, 6, 1, 2, 3, 6, 5], [3, 4, 5, 6, 1, 2, 3, 4, 6, 6], [4, 5, 6, 1, 2, 3, 4, 5, 1, 1]] start_points = [(0, 0), (1, 0)] end_points = [(9, 9), (9, 8)] 正确输出: 每一步改变的颜色: [3, 6, 1] 颜色改变次数: 3