You are given a n x n array of integers where each position contains a 1 or 0.
1 represents land and 0 represents water.
You walk from the top of the input to the bottom using the shortest land path.
You can move up, down, left or right (no diagonal movements).
Modify the array so that every cell not on the shortest land path is water.
"""
input = [
[1,0,0,1,0],
[1,1,1,1,0],
[1,0,1,0,0],
[0,1,1,0,1],
[0,1,0,0,0]
]

output = [
[0,0,0,1,0],
[0,0,1,1,0],
[0,0,1,0,0],
[0,1,1,0,0],
[0,1,0,0,0]
]

Follow up:

Part 2: Now you are given a 2D array of integersSt where each position contains 0-9.
The number 0 still represents water and values 1-9 represent the cost of
traversing that piece of land. Return an array containing the land used in the
lowest cost path.
E.g.

int[][] input = {

{2,0,0,1,0},

{2,0,1,1,0},

{2,0,1,0,0},

{2,0,1,1,1},

{2,0,0,2,0}

};

int[][] output = {
{0,0,0,1,0},
{0,0,1,1,0},
{0,0,1,0,0},
{0,0,1,1,0},
{0,0,0,2,0}
};

This is the lowest cost path (cost = 8). Can someone please help solving this question?