Advertisement
sashomaga

Depth first search implementation

Jan 15th, 2013
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.66 KB | None | 0 0
  1. using System;
  2. //Write a program that finds the largest area of equal neighbor elements in a rectangular matrix and prints its size
  3. class Program
  4. {
  5.     static int[,] matrix = {
  6.                            {1,3,2,2,2,4},
  7.                            {3,3,3,2,4,4},
  8.                            {1,3,1,2,3,3},
  9.                            {4,3,1,3,3,1},
  10.                            {4,3,3,3,1,1}, //not work for value 0 coz zero is used to mark
  11.                            };
  12.     static int model;
  13.     static int score = 0;
  14.     static int bestScore = 0;
  15.     static int bestModel;
  16.  
  17.  
  18.     static void Main()
  19.     {
  20.         for (int x = 0; x < matrix.GetLength(0); x++)
  21.         {
  22.             for (int y = 0; y < matrix.GetLength(1); y++)
  23.             {
  24.                 model = matrix[x,y];
  25.                 score = 0;
  26.                 CheckPoint(x, y);
  27.             }
  28.         }
  29.         Console.WriteLine(bestScore+" "+bestModel);
  30.     }
  31.    
  32.     private static void CheckPoint(int x, int y)
  33.     {
  34.         //bottom of recursion
  35.         if (x < 0 || x >= matrix.GetLength(0) || y < 0 || y >= matrix.GetLength(1))
  36.         {
  37.             return;
  38.         }
  39.         if (matrix[x,y] != model)
  40.         {
  41.             return;
  42.         }
  43.         //count score
  44.         score++;
  45.         if (score > bestScore)
  46.         {
  47.             bestScore = score;
  48.             bestModel = model;
  49.         }
  50.  
  51.         matrix[x, y] = 0; //mark as visited
  52.         //call recursion for all directions
  53.         CheckPoint(x, y+1); //rigth
  54.         CheckPoint(x+1, y); //down
  55.         CheckPoint(x, y-1); //left
  56.         CheckPoint(x-1, y); // up        
  57.         matrix[x, y] = model; //unmark
  58.  
  59.     }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement