小编Fel*_*ipe的帖子

我有网格N×M,其中每个单元格用一种颜色着色.

当玩家点击颜色α网格的任何单元格时,网格最左上角的颜色为β的单元格接收颜色α,但不仅仅是:所有那些通过颜色连接到源的单元格仅使用颜色α或β的路径也接收颜色α.

应仅在水平和垂直方向上考虑单元之间的连接以形成路径.例如,当玩家点击左图中突出显示的单元格时,网格会在右侧接收图形的颜色.游戏的目标是使网格单色化.

输入描述

输入的第一行由2个整数N和M(1≤N≤4,1≤M≤5)组成,它们分别代表网格的行数和列数.下面的N行描述了网格的初始配置,用0到9之间的整数表示每种颜色.输入不包含任何其他行.

输出描述

打印包含单个整数的行,该整数表示播放器必须执行的最小点击次数才能使网格变为单色.

输入样本

1:

4 5
01234
34567
67890
90123

2:

4 5
01234
12345
23456
34567

3:

4 5
00162
30295
45033
01837

输出样本

1:

12

2:

7

3:

10

我正在尝试找回带回溯的解决方案(因为8秒的时间限制和网格的小尺寸).但它超出了时间限制.有些人刚刚在0秒时完成了它.

还有其他算法可以解决这个问题吗？

#include <stdio.h>
#include <string.h>

#define MAX 5
#define INF 999999999

typedef int signed_integer;

signed_integer n,m,mink;
bool vst[MAX][MAX];

signed_integer flood_path[4][2] = {
    {-1,0},
    {1,0},
    {0,1},
    {0,-1}
};

//flood and paint all possible cells... the root is (i,j)
signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i, signed_integer j, …

给定具有正整数值和整数K的网格.K个连通元素的最大总和是多少？

以下是K值为6 的5x5矩阵的示例.

有人可以帮我识别这个问题吗？我该如何开始解决它？
我知道的唯一方法是对该矩阵的每个单元格进行深度优先搜索.但我认为这不是最好的方法.

不允许重复细胞.

此处连接仅表示单元格水平或垂直相邻

给定加权无向图G和两个节点U,V以获得最短路径.如何获得从U到V的最短路径,使用偶数个边缘(如果可能的话)？

我在网上发现了一些文章,说原始图表上的修改是必要的.但我无法理解如何做到这一点.

有一些很好的材料可以研究这个问题吗？

假设给出一个包含 n 个整数的列表（该列表不需要已经排序）。如何检查删除、更新或插入值后列表是否已排序（非递增或非递减）？

我能想到解决这个问题的唯一方法是通过删除[O(n)]、插入[O(n)]和更新[O(n)]操作来保留数字的链表以及线性检查查看其排序是非递减还是非递增。有可能更快地解决这个问题吗？

删除、插入和更新意味着用户将给出一个要删除/插入/更新的位置，并且将在给定位置上插入、删除或添加值。

随时都会对输入进行查询，询问列表处于哪种状态（非递增或非递减）