二维阵列游戏 - 走路并找到c＃

Question

我的c＃编程任务有问题。我有一个NxM（N：rows，M：cols）矩阵。机器人正在穿过矩阵，他可以向下或向右（不允许对角线移动）并始终从最左上角开始。机器人从他经过的每个细胞中收集“宝藏”。为他分配了一些收集点，他必须将珍宝带到收集点（在达到一个之后，他不能再往前走）。我的任务是确定哪些CP可以携带最多的宝物，以及有多少。我也对进程有限制：max runtime 0.2 sec和max used RAM 32 MB。

就我而言，我需要遍历每个CP，寻找每条路径，然后计算每条路径的宝藏，搜索最大值，然后搜索具有最大最大值的CP。

我错过了如何收集给定CP的每条路径。

当前代码：

        string[] firstline = Console.ReadLine().Split(new char[] { ' ' });
        int N = Convert.ToInt32(firstline[0]); // N
        int M = Convert.ToInt32(firstline[1]); // M
        int K = Convert.ToInt32(firstline[2]); // no of treasures
        int G = Convert.ToInt32(firstline[3]); // no of CPs

        int[,] TREASURES = new int[K, 2]; // collecting the location for each tres
        for (int i = 0; i < K; i++)
        {
            string[] line = Console.ReadLine().Split(new char[] { ' ' });
            TREASURES[i, 0] = Convert.ToInt32(line[0]); // row
            TREASURES[i, 1] = Convert.ToInt32(line[1]); // col
        }

        int[,] CPS = new int[G, 2]; // same for CPs
        for (int i = 0; i < G; i++)
        {
            string[] line = Console.ReadLine().Split(new char[] { ' ' });
            CPS[i, 0] = Convert.ToInt32(line[0]);
            CPS[i, 1] = Convert.ToInt32(line[1]);
        }

        (...)

        int C = 0; // The count of max treasures
        int CP = 0; // The answer CP's index
        Console.WriteLine(C);
        Console.WriteLine("{0} {1}", CPS[CP,0], CPS[CP,1]);

Answer 1

你真的不需要找到所有可能的方法，只有最好的方法。所以首先找到长度为1的最佳方式，然后从那些 - 长度为2的最佳方法，等等。

你需要实现一个叫做“wave”的算法（又名广度优先搜索）。从第一个单元格开始，为所有相邻单元格指定一个值（得分），将它们放入列表中并继续通过该列表，直到您评估矩阵中的所有单元格。

看看这里简单的实现（类似的，不一样的）问题：https://github.com/zdanev/mazekata