15,850,103 members
See more:
The original question can be found here, I've decided to create a new thread, since the old one was getting very confusing for newcomers

I have a 2D matrix, that may look something like this:
```0 1 2
5 4 3
7 8 9```

I'm trying to find a path that contains the highest number of segments, where the value decreases, so that when we find our path the following parameter is true:
`finalPath[0] > finalPath[1]`

This, on it's own has, as far as I know, been solved, but I also have to account for segments, where the value stays the same, this can be described in the following expression
`finalPath[0] == finalPath[1]`

SOME OTHER RULES AND DEFINITIONS:
- The highest value in the matrix does not have to be the optimal starting point.
- We can only move in the 4 cardinal directions (up, down, left, right)
- We may not visit an already visited cell
- A 'segment' refers to two elements next to each other (ie. matrix[0][0] and matrix[1][0] form a segment, the value different between these elements is what we are examining)
- The correct starting point can be located anywhere in the matrix

FINAL GOAL OF THE ALGORITHM: Minimize the number of straight segments and maximize the number of segments where the value decreases.
Note that the 'direction' of the path is irrelevant

TEST SCENARIOS:
```0 1 2
5 4 3
7 8 9```

Final path:
`[9, 8, 7, 5, 4, 3, 2, 1, 0]`
(All path segments are decreasing, this is the simplest scenario)
```0 1 2
2 2 2
3 4 5```

Final path:
`[5, 4, 3, 2, 2, 1, 0]`
(We do not traverse all of the elements, since we are looking to maximize the number of decreasing segments)

What I have tried:

See the old question for what I've tried so far.
Posted
Updated 29-Jan-23 1:44am
v2
Gerry Schmitz 26-Jan-23 13:48pm
Add 2 extra rows and colums (5x5). Then you can use one function to iterate the interior 3x3 matrix (in terms of x-1, y; x, y-1; x+1, y; x, y+1) without having to get too fancy (cell is invalid, same, higher, lower).

## Solution 1

Below are the changes in my previous solution to get the result that you wanted.

Form this:
C#
```if ((testValue == currentValue || testValue == currentValue - 1) &&
Math.Max(nextValue, testValue) == testValue)
{
nextValue = testValue;
nextCell = new[] { cell[0], cell[1] };
}```

To this:
C#
```if (testValue == currentValue || testValue == currentValue - 1)
{
nextValue = testValue;
nextCell = new[] { cell[0], cell[1] };
if (Math.Min(nextValue, testValue) == testValue)
break;
}```

And changed to order of direction checks from:
C#
```if (direction == 0) // left
return cc == 0 ? default : new[] { cr, --cc };

if (direction == 1) // right
return cc == cols - 1 ? default : new[] { cr, ++cc };

if (direction == 2) // down
return cr == 0 ? default : new[] { --cr, cc };

if (direction == 3) // up
return cr == rows - 1 ? default : new[] { ++cr, cc };```

To:
C#
```if (direction == 0) // left
return cc == 0 ? default : new[] { cr, --cc };

if (direction == 1) // up
return cr == rows - 1 ? default : new[] { ++cr, cc };

if (direction == 2) // down
return cr == 0 ? default : new[] { --cr, cc };

if (direction == 3) // right
return cc == cols - 1 ? default : new[] { cr, ++cc };```

Full code below:
C#
```int[,] cells1 =
{
{ 1, 2, 3 },
{ 6, 5, 4 },
{ 7, 8, 9 }
};

int[]? result1 = ProcessCells(cells1);
DisplayResults(cells1, result1);

int[,] cells2 =
{
{ 0, 1, 2 },
{ 2, 2, 2 },
{ 3, 4, 5 }
};

int[]? result2 = ProcessCells(cells2);
DisplayResults(cells2, result2);

int[,] cells3 =
{
{ 6, 6, 6 },
{ 5, 8, 7 },
{ 4, 8, 9 }
};

int[]? result3 = ProcessCells(cells3);
DisplayResults(cells3, result3);

// test a single cell matrix
int[,] singleCells =
{
{ 1 }
};

int[]? singleResult = ProcessCells(singleCells);
DisplayResults(singleCells, singleResult);

//test a large matrices
int[,] largeMatrix1 =
{
{ 8, 9, 10, 11, 12, 13, },
{ 7, 16, 15, 14, 14, 14, },
{ 6, 17, 30, 31, 32, 33, },
{ 5, 18, 29, 26, 25, 34, },
{ 4, 19, 28, 27, 24, 35, },
{ 3, 20, 21, 22, 23, 36, },
};

int[]? largeResult1 = ProcessCells(largeMatrix1);
DisplayResults(largeMatrix1, largeResult1);

int[,] largeMatrix2 =
{
{ 1, 1, 1, 1, 1, 2, },
{ 1, 3, 2, 2, 2, 2, },
{ 1, 3, 8, 8, 8, 8, },
{ 1, 4, 7, 6, 6, 9, },
{ 1, 4, 7, 6, 6, 9, },
{ 0, 4, 5, 5, 5, 9, },
};

int[]? largeResult2 = ProcessCells(largeMatrix2);
DisplayResults(largeMatrix2, largeResult2);

// test a solution that can not be completed
{
{ 0, 0, 3 },
{ 6, 0, 4 },
{ 7, 8, 9 }
};

static int[]? ProcessCells(int[,] cells)
{
// get the bounds of the array
int rows = cells.GetLength(0);
int cols = cells.GetLength(1);

// is the array valid?
if (rows < 1) return default;
if (cols < 1) return default;

// remember where we have been...
int[,] path = new int[rows, cols];

// track the results
int[] results = new int[rows * cols];

// initialize results to failed
for (int i = 0; i < results.Length; i++)
results[i] = -1;

// initialize the starting value and cell
int startValue = cells[rows - 1, cols - 1];
int currentValue = startValue;
int[] currentCell = {rows - 1, cols - 1};
path[rows - 1, cols - 1] = -1;

// set pointer to start of results
int index = 0;

// log the start cell
results[index] = cells[currentCell[0], currentCell[1]];

// now walk the 2D array
while (currentCell[0] >= 0 && currentCell[1] >= 0)
{
// track valid cell
int[]? nextCell = default;
int nextValue = -1;

// look around
for (int direction = 0; direction < 4; direction++)
{
// get the adjacent cell that we want to look at
int[]? cell = GetValidAdjacentCell(direction, currentCell, rows, cols);

// check if not a valid direction
if(cell is null ||  path[cell[0], cell[1]] != 0)
continue;

int testValue = cells[cell[0], cell[1]];

// do we have a valid value?
if (testValue == currentValue || testValue == currentValue - 1)
{
nextValue = testValue;
nextCell = new[] { cell[0], cell[1] };
if (Math.Min(nextValue, testValue) == testValue)
break;
}
}

// no more to do
if (nextCell is null)
break;

// track value
results[++index] = cells[nextCell[0], nextCell[1]];

// track where we are
currentCell = new[] { nextCell[0], nextCell[1] };
currentValue = nextValue;

// track where we have been
path[nextCell[0], nextCell[1]] = -1;
}

// we are all done
return results;
}

static int[]? GetValidAdjacentCell(int direction, int[] currentCell, int rows, int cols)
{
int cr = currentCell[0];
int cc = currentCell[1];

// check based on importance of order

if (direction == 0) // left
return cc == 0 ? default : new[] { cr, --cc };

if (direction == 1) // up
return cr == rows - 1 ? default : new[] { ++cr, cc };

if (direction == 2) // down
return cr == 0 ? default : new[] { --cr, cc };

if (direction == 3) // right
return cc == cols - 1 ? default : new[] { cr, ++cc };

// invalid direct value
return default;
}

static void DisplayResults(int[,] cells, int[]? path)
{
int rows = cells.GetLength(0);
int cols = cells.GetLength(1);

int padLeft = cells[rows - 1, cols - 1].ToString().Length + 1;

Console.WriteLine("Matrix Traversed:");
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)

Console.WriteLine();
}
Console.WriteLine();

Console.WriteLine(\$"Path found: {string.Join(", ", path.Where(x => x > -1))}");

Console.WriteLine();
}```

and the output:
```Matrix Traversed:
1 2 3
6 5 4
7 8 9

Path found: 9, 8, 7, 6, 5, 4, 3, 2, 1

Matrix Traversed:
0 1 2
2 2 2
3 4 5

Path found: 5, 4, 3, 2, 2, 1, 0

Matrix Traversed:
6 6 6
5 8 7
4 8 9

Path found: 9, 8, 8, 7, 6, 6, 6, 5, 4

Matrix Traversed:
1

Path found: 1

Matrix Traversed:
8  9 10 11 12 13
7 16 15 14 14 14
6 17 30 31 32 33
5 18 29 26 25 34
4 19 28 27 24 35
3 20 21 22 23 36

Path found: 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 14, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3

Matrix Traversed:
1 1 1 1 1 2
1 3 2 2 2 2
1 3 8 8 8 8
1 4 7 6 6 9
1 4 7 6 6 9
0 4 5 5 5 9

Path found: 9, 9, 9, 8, 8, 8, 8, 7, 7, 6, 5, 5, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 0

Matrix Traversed:
0 0 3
6 0 4
7 8 9

Path found: 9, 8, 7, 6```

As for longest horizontal/vertical segment, I leave that to you.

v2