using System;

using System.Collections.Generic;

​

public class Program

{

    private static int count = 0;

    public static void Main()

    {

        int[,] matrix = new int[4,4];

        for(int i = 0; i < matrix.GetLength(0) -1 ; i++)

        {

            for(int j = 0; j < matrix.GetLength(1) -1 ; j++)

            {

                matrix[i,j] = 0;

            }

        }

        LinkedList<Tuple<int, int>> path = new LinkedList<Tuple<int, int>>();

        //FindAllPaths(matrix, 0, 0, path);

        Console.WriteLine("Count: {0}", count);

    }

    private static void FindAllPaths(int[,] matrix, int i , int j, LinkedList<Tuple<int, int>> Path)

    {

        Path.AddLast(new Tuple<int, int>(i, j));

        if(i == matrix.GetLength(0) -1 && j == matrix.GetLength(1) - 1)

        {

            count++;

            PrintPath(Path);

        }

        if(i + 1 <= matrix.GetLength(0) - 1)

        {

            FindAllPaths(matrix, i + 1, j, Path);

        }

        if(j + 1 <= matrix.GetLength(1) -1)

        {

            FindAllPaths(matrix, i, j + 1, Path);

        }

        Path.RemoveLast();

    }

    private static void PrintPath(LinkedList<Tuple<int, int>> path)

    {

        Console.Write("Path:");

        foreach(var point in path)

        {

            Console.Write("({0},{1})->", point.Item1, point.Item2);

        }

        Console.WriteLine("");

    }

}