Given m x n matrix, print all the possible paths from top to down

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] inputMatrix = new int[,]
            {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
            };
            for (int i = 0; i < inputMatrix.GetLength(1); i++)
            {
                MatrixTraversalTopDown(inputMatrix, inputMatrix[0, i].ToString(), 0, i);
            }

        }
        public static void MatrixTraversalTopDown(int[,] inputMatrix, string path, int row, int col)
        {
            if (row == inputMatrix.GetLength(0) - 1)
            {
                //Display the traversal path
                Console.WriteLine(path);
                return;
            }
            //Botton Left
            if (row + 1 < inputMatrix.GetLength(0) && col - 1 >= 0)
            {
                MatrixTraversalTopDown(inputMatrix, path + " - " + inputMatrix[row + 1, col - 1].ToString(), row + 1, col - 1);
            }
            //Bottom
            if (row + 1 < inputMatrix.GetLength(0))
            {
                MatrixTraversalTopDown(inputMatrix, path + " - " + inputMatrix[row + 1, col].ToString(), row + 1, col);
            }
            //Bottom Right
            if (row + 1 < inputMatrix.GetLength(0) && col + 1 < inputMatrix.GetLength(1))
            {
                MatrixTraversalTopDown(inputMatrix, path + " - " + inputMatrix[row + 1, col + 1].ToString(), row + 1, col + 1);
            }
        }
    }
}
Output
==========
1 - 4 - 7
1 - 4 - 8
1 - 5 - 7
1 - 5 - 8
1 - 5 - 9
2 - 4 - 7
2 - 4 - 8
2 - 5 - 7
2 - 5 - 8
2 - 5 - 9
2 - 6 - 8
2 - 6 - 9
3 - 5 - 7
3 - 5 - 8
3 - 5 - 9
3 - 6 - 8
3 - 6 - 9
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s