CODEWITHSUNDEEP
c#algorithmmatrix
benyogyerek
benyogyerek

Reputation: 426

Two dimensional array game - walk and find c#

I'm having trouble with my c# programming assignment. I have a NxM (N: rows, M: cols) matrix. A robot is walking through the matrix, he can go either down or right (no diagonal movement allowed) and always starts from the topmost leftmost corner. The robot is collecting "treasure" from each cell he goes across. Some collecting points are assigned for him and he has to carry the treasures to a collecting point (and after reaching one, he can't go further). My task is to determine into which CP the most treasures can be carried and how many is that. I also have restrictions for the process: max runtime 0.2 sec and max used RAM 32 MB.

As far as I have concerned, I need to loop through every CP, looking for every path, then counting the treasures for each path, search for maximum and then search for the CP having the greatest max value.

I am missing how I can collect every path for given CP.

Current code:

        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]);

Upvotes: 1

Views: 1386

Answers (1)

Z .
Z .

Reputation: 12837

you don't really need to find all possible ways, only the best ones. so first find the best possible ways with length 1, then from those - the best ones with length 2, etc.

you need to implement an algorithm called "wave" (aka breadth-first search). starting from the first cell, assign a value (score) to all neighboring cells, put those in a list and continue working thru that list, till you evaluate all cells in the matrix.

look at simple implementation (of similar, not the same) problem here: https://github.com/zdanev/mazekata

Upvotes: 2

Related Questions