Shortest Path in binary matrix

README.txt

This problem was asked by Google.

You are given an M by N matrix consisting of booleans that represents a board. 
Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, 
return the minimum number of steps required to reach the end coordinate from the start. 
If there is no possible path, then return null. You can move up, left, down, and right. 
You cannot move through walls. You cannot wrap around the edges of the board.

For example, given the following board:

[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]

and start = (3, 0) (bottom left) and end = (0, 0) (top left), 
the minimum number of steps required to reach the end is 7, 
since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Program.cs

class Program
{
    static void Main(string[] args)
    {
        bool[][] matrix = new bool[][]
        {
            new bool[] {false, false, false, false },
            new bool[] {true,  true,  false, true  },
            new bool[] {false, false, false, false },
            new bool[] {false, false, false, false },
        };
        Console.WriteLine(Bfs(matrix, 3, 0, 0, 0)); // 7
    }

    private static int Bfs(bool[][] matrix, int row, int column, int destinationRow, int destinationColumn)
    {
        int[,] directions = new int[,]
        {
            { 0, 1},
            { 0, -1},
            { 1, 0},
            { -1, 0},
        };

        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(new Node(row, column));
            
        while(queue.Count > 0)
        {
            var node = queue.Dequeue();
            node.Visit();
            for (int i = 0; i <= directions.GetUpperBound(0); i++)
            {
                var expandedNode = new Node(node, directions[i, 0], directions[i, 1]);

                // we catch it!
                if (expandedNode.Row == destinationRow && expandedNode.Column == destinationColumn)
                {
                    return expandedNode.Depth;
                }

                if (expandedNode.IsInArrayRange(matrix) && (!expandedNode.Visited) && (!matrix[expandedNode.Row][expandedNode.Column]))
                {
                    queue.Enqueue(expandedNode);
                }
            }
        }
        return -1;
    }
}

class Node : IEquatable<Node>
{
    public Node(int row, int column) : this(row, column, 0) { }

    public Node(int row, int column, int depth)
    {
        Row = row;
        Column = column;
        Depth = depth;
    }

    public Node(Node node, int step1, int step2)
        : this(node.Row + step1, node.Column + step2, node.Depth + 1)
    {
    }

    public int Row { get; private set; }
    public int Column { get; private set; }
    public int Depth { get; private set; }
    public bool Visited { get; private set; }

    public void Visit()
    {
        this.Visited = true;
    }

    public override bool Equals(object obj)
    {
        return Equals(obj as Node);
    }

    public bool Equals(Node other)
    {
        return other != null &&
                Row == other.Row &&
                Column == other.Column;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Row, Column);
    }

    internal bool IsInArrayRange(bool[][] matrix)
    {
        return this.Row >= 0 && this.Row < matrix.Length &&
            this.Column >= 0 && this.Column < matrix[0].Length;
    }
}