Pattern matching in a matrix

You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.

eg :

Matrix
{‘A’,’C’,’P’,’R’,’C’},
{‘X’,’S’,’O’,’P’,’C’},
{‘V’,’O’,’V’,’N’,’I’},
{‘W’,’G’,’F’,’M’,’N’},
{‘Q’,’A’,’T’,’I’,’T’}

And pattern is MICROSOFT.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {   
            string[,] inputMatrix = new string[,]
            {
                {"A", "C", "P", "R", "C"},
                {"X", "S", "O", "P", "C"},
                {"V", "O", "V", "N", "I"},
                {"W", "G", "F", "M", "N"},
                {"Q", "A", "T", "I", "T"}
            };
            Console.WriteLine("Given Matrix: ");
            Console.WriteLine("==============");
            for (int i = 0; i < inputMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < inputMatrix.GetLength(1); j++)
                {
                    Console.Write(inputMatrix[i, j] + " ");
                }
                Console.WriteLine();
            }
            string pattern = "MICROSOFT";
            Console.WriteLine();
            Console.WriteLine("Given Pattern: ");
            Console.WriteLine("===============");
            Console.WriteLine(pattern);
            Console.WriteLine();
            List<Coordinate> coordinateList = new List<Coordinate>();
            int found = 0;
            for (int i = 0; i < inputMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < inputMatrix.GetLength(1); j++)
                {
                    //Check for root
                    coordinateList.Clear();
                    if (inputMatrix[i, j] == pattern[0].ToString())
                    {
                        Coordinate c = new Coordinate(i, j);
                        coordinateList.Add(c);
                        checkVicinity(c, inputMatrix, coordinateList, pattern, 1);
                        if (coordinateList.Count == pattern.Length)
                        {
                            Console.WriteLine("Given Pattern Found!!! and Coordinates are: ");
                            Console.WriteLine("============================================");
                            for (int k = 0; k < coordinateList.Count; k++)
                            {
                                Console.WriteLine(coordinateList[k].row + " , " + coordinateList[k].col + " --> " + inputMatrix[coordinateList[k].row, coordinateList[k].col]);
                            }
                            found = 1;
                            break;
                        }
                    }
                }
                if (found == 1)
                    break;
            }
            if (found == 0)
                Console.WriteLine("Sorry, Given Pattern *NOT* Found!!!");
            Console.WriteLine();
        }
        public static void checkVicinity(Coordinate c, string[,] matrix, List<Coordinate> coordinateList, string pattern, int index)
        {
            if (coordinateList.Count == pattern.Length) 
                return;
            Coordinate nc = new Coordinate();
            nc = getLeftCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getTopLeftCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getTopCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getTopRightCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getRightCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getBottomRightCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getBottomCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            nc = getBottomLeftCoordinate(c, matrix);
            if (!coordinateList.Contains(nc) && nc.row != -1 && nc.col != -1)
            {
                if (matrix[nc.row, nc.col] == pattern[index].ToString())
                {
                    coordinateList.Add(nc);
                    checkVicinity(nc, matrix, coordinateList, pattern, index + 1);
                    if (coordinateList.Count == pattern.Length)
                        return;
                    coordinateList.Remove(nc);
                }
            }
            return;
        }
        public static Coordinate getLeftCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.col - 1 >= 0)
            {
                adjacent.row = c.row;
                adjacent.col = c.col - 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getTopLeftCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.col - 1 >= 0 && c.row - 1 >= 0)
            {
                adjacent.row = c.row - 1;
                adjacent.col = c.col - 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getTopCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.row - 1 >= 0)
            {
                adjacent.row = c.row - 1;
                adjacent.col = c.col;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getTopRightCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.col + 1 < matrix.GetLength(1) && c.row - 1 >= 0)
            {
                adjacent.row = c.row - 1;
                adjacent.col = c.col + 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getRightCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.col + 1 < matrix.GetLength(1))
            {
                adjacent.row = c.row;
                adjacent.col = c.col + 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getBottomRightCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.row + 1 < matrix.GetLength(0) && c.col + 1 < matrix.GetLength(1))
            {
                adjacent.row = c.row + 1;
                adjacent.col = c.col + 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getBottomCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.row + 1 < matrix.GetLength(0))
            {
                adjacent.row = c.row + 1;
                adjacent.col = c.col;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public static Coordinate getBottomLeftCoordinate(Coordinate c, string[,] matrix)
        {
            Coordinate adjacent = new Coordinate();
            if (c.row + 1 < matrix.GetLength(0) && c.col - 1 >= 0)
            {
                adjacent.row = c.row + 1;
                adjacent.col = c.col - 1;
                return adjacent;
            }
            else
            {
                adjacent.row = -1;
                adjacent.col = -1;
                return adjacent;
            }
        }
        public class Coordinate
        {
            public int row;
            public int col;
            public Coordinate()
            {
                row = 0;
                col = 0;
            }
            public Coordinate(int row, int col)
            {
                this.row = row;
                this.col = col;
            }
            public override bool Equals(object obj)
            {
                if (obj == null)
                    return false;
                Coordinate c = obj as Coordinate;
                if ((Object)c == null)
                    return false;
                return (c.row == row && c.col == col);
            }
            public override int GetHashCode() 
            { 
                return string.Format("{0}_{1}", row.ToString(), col.ToString()).GetHashCode(); 
            } 
        }
    }
}
Given Matrix:
==============
A C P R C
X S O P C
V O V N I
W G F M N
Q A T I T
Given Pattern:
===============
MICROSOFT
Given Pattern Found!!! and Coordinates are:
============================================
3 , 3 --> M
2 , 4 --> I
1 , 4 --> C
0 , 3 --> R
1 , 2 --> O
1 , 1 --> S
2 , 1 --> O
3 , 2 --> F
4 , 2 --> T
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