using System;

​

public class Program

{

    public static void Main()

    {

        var row = 4;

        var column = 4;

        int[, ] mazMatrixSol = new int[row, column];

        int[, ] mazMatrix = {{1, 0, 0, 0}, {1, 1, 0, 0}, {0, 1, 0, 0}, {1, 1, 1, 1}};

        if (!SolveMazRecur(mazMatrix, 0, 0, mazMatrixSol))

        {

            Console.WriteLine("Solution Doesn't exist");

        }

​

        printSolution(mazMatrixSol);

    }

​

    public static bool IsSafe(int[, ] maze, int row, int col)

    {

        return maze[row, col] == 1 && row >= 0 && row < maze.GetLength(0) && col >= 0 && col < maze.GetLength(1);

    }

​

    public static bool SolveMazRecur(int[, ] maze, int row, int col, int[, ] solution)

    {

        //base condition, may be we have the last row & last column

        if (row == maze.GetLength(0) - 1 && col == maze.GetLength(1) - 1)

        {

            solution[row, col] = 1;

            return true;

        }

​

        if (IsSafe(maze, row, col))

        {

            if (solution[row, col] == 1)

                return false;

            solution[row, col] = 1;

            if (SolveMazRecur(maze, row, col + 1, solution))

                return true;

            if (SolveMazRecur(maze, row + 1, col, solution))

                return true;

            if (SolveMazRecur(maze, row - 1, col, solution))

                return true;

            if (SolveMazRecur(maze, row, col - 1, solution))

                return true;

            solution[row, col] = 0;

            return false;

        }

​

        return false;

    }

​

    static void printSolution(int[, ] sol)

    {

        for (int i = 0; i < sol.GetLength(0); i++)

        {

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

                Console.Write(" " + sol[i, j] + " ");

            Console.WriteLine();

        }

    }

}