You have not specified a language, so I am guessing that you want a pseudo-code solution.
It would be something like the following
1. store current value (var_next)
2. check adjacent cells for equal to the (var_next) or less while skipping over the (var_last) cell
- true, store value to (var_next)
3. once completed all checks:
- store the current value to (var_last)
- move to (var_next)
4. repeat steps 1. to 3. until there are no more cells to move to.
If you are looking for a different type of answer, then please update your question.
UPDATE
There was a little more to this than I thought. Needed to also track the path taken.
Here is the solution that I came up with. It's written in C#:
1. Tests used:
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);
int[,] singleCells =
{
{ 1 }
};
int[]? singleResult = ProcessCells(singleCells);
DisplayResults(singleCells, singleResult);
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);
int[,] badCells =
{
{ 0, 0, 3 },
{ 6, 0, 4 },
{ 7, 8, 9 }
};
int[]? badResult = ProcessCells(badCells);
DisplayResults(badCells, badResult);
And here is the code:
static int[]? ProcessCells(int[,] cells)
{
int rows = cells.GetLength(0);
int cols = cells.GetLength(1);
if (rows < 1) return default;
if (cols < 1) return default;
int[,] path = new int[rows, cols];
int[] results = new int[rows * cols];
for (int i = 0; i < results.Length; i++)
results[i] = -1;
int startValue = cells[rows - 1, cols - 1];
int currentValue = startValue;
int[] currentCell = {rows - 1, cols - 1};
path[rows - 1, cols - 1] = -1;
int index = 0;
results[index] = cells[currentCell[0], currentCell[1]];
while (currentCell[0] >= 0 && currentCell[1] >= 0)
{
int[]? nextCell = default;
int nextValue = -1;
for (int direction = 0; direction < 4; direction++)
{
int[]? cell = GetValidAdjacentCell(direction, currentCell, rows, cols);
if(cell is null || path[cell[0], cell[1]] != 0)
continue;
int testValue = cells[cell[0], cell[1]];
if ((testValue == currentValue || testValue == currentValue - 1) &&
Math.Max(nextValue, testValue) == testValue)
{
nextValue = testValue;
nextCell = new[] { cell[0], cell[1] };
}
}
if (nextCell is null)
break;
results[++index] = cells[nextCell[0], nextCell[1]];
currentCell = new[] { nextCell[0], nextCell[1] };
currentValue = nextValue;
path[nextCell[0], nextCell[1]] = -1;
}
return results;
}
static int[]? GetValidAdjacentCell(int direction, int[] currentCell, int rows, int cols)
{
int cr = currentCell[0];
int cc = currentCell[1];
if (direction == 0)
return cc == 0 ? default : new[] { cr, --cc };
if (direction == 1)
return cc == cols - 1 ? default : new[] { cr, ++cc };
if (direction == 2)
return cr == 0 ? default : new[] { --cr, cc };
if (direction == 3)
return cr == rows - 1 ? default : new[] { ++cr, cc };
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.Write(cells[row, col].ToString().PadLeft(padLeft));
Console.WriteLine();
}
Console.WriteLine();
int count = path.Count(value => value != -1);
if (path.Length != count)
Console.WriteLine($"Path cannot be completed. Only traversed {count} cells of {path.Length}");
Console.WriteLine($"Path found: {string.Join(", ", path)}");
Console.WriteLine();
}
3. 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, 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, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0
Matrix Traversed:
0 0 3
6 0 4
7 8 9
Path cannot be completed. Only traversed 4 cells of 9
Path found: 9, 8, 7, 6, -1, -1, -1, -1, -1
The last test will fail as it has no complete path.
All code is fully commented.
Enjoy!