# C# Solution

• ``````    public class Node
{
public int Row { get; set; }
public int Col { get; set; }
public Node(int r, int c)
{
Row = r;
Col = c;
}
public List<Node> Children { get; set; } = new List<Node>();
}
public class GolfTree : Node, IComparable<GolfTree>
{
public int Height { get; set; }
public GolfTree(int r, int c, int h)
: base(r, c)
{
Height = h;
}

public int CompareTo(GolfTree other)
{
return Height.CompareTo(other.Height);
}
}
public class Solution
{
bool[,] IsVisited;
int[,] ShortestDistances;

Node[,] Graph { get; set; }
List<GolfTree> Trees { get; set; } = new List<GolfTree>();
void BuildGraph (IList<IList<int>> forest )
{
int nRows = forest.Count;
int nCols = forest[0].Count;

Graph = new Node[nRows, nCols];

for (int i=0; i<nRows; ++i)
{
for (int j=0; j<nCols; ++j)
{
if (forest[i][j] == 0)
{
Graph[i, j] = null;
continue;
}

var node = new Node(i, j);
Graph[i, j] = node;

if (i > 0) // up possible
{
var up = Graph[i - 1, j];
if (up != null )
{
}
}
if ( j > 0 ) // left possible
{
var left = Graph[i, j -1 ];
if (left != null)
{
}
}

if (forest[i][j] > 1)
{
}
}
}
}

int computeDistance (Node start, Node end, IList<IList<int>> forest)
{
if (forest[start.Row][start.Col] == 0)
return -1;

int height = forest.Count;
int width = forest[0].Count;

IsVisited = new bool[height, width];
ShortestDistances = new int[height, width];

for (int i=0; i<height; i++)
{
for (int j=0; j<width; ++j)
{
ShortestDistances[i, j] = int.MaxValue;
}
}

var currentPositions = new List<Node>();
ShortestDistances[start.Row, start.Col] = 0;

while (currentPositions.Count > 0)
{
var nextPositions = new List<Node>();

foreach (var curPos in currentPositions)
{
if (curPos.Row == end.Row && curPos.Col == end.Col)
return ShortestDistances[curPos.Row, curPos.Col];

if (IsVisited[curPos.Row, curPos.Col])
continue;

var new_distance = ShortestDistances[curPos.Row, curPos.Col] + 1;

foreach (var nextPos in curPos.Children )
{
if (!IsVisited[nextPos.Row, nextPos.Col] &&
new_distance <= ShortestDistances[nextPos.Row, nextPos.Col])
{
ShortestDistances[nextPos.Row, nextPos.Col] = new_distance;
}
}

IsVisited[curPos.Row, curPos.Col] = true;
}

currentPositions = nextPositions;
}

return -1;
}
public int CutOffTree(IList<IList<int>> forest)
{
if (forest[0][0] == 0)
return -1;

int nRow = forest.Count;
int nCol = forest[0].Count;

BuildGraph(forest);

Trees.Sort();

var start = Graph[0,0];
int totalWalk = 0;

foreach (var tree in Trees)
{
var end = Graph[tree.Row, tree.Col];
var walk = computeDistance(start, end, forest);
if (walk == -1)
return -1;
forest[end.Row][end.Col] = 1;
totalWalk += walk;
start = end;
}