Advertisement
ScorpS

Depth First Search Largest Area

Jan 15th, 2013
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.82 KB | None | 0 0
  1. //* Write a program that finds the largest area of equal neighbor elements in
  2. //a rectangular matrix and prints its size.
  3.  
  4. using System;
  5.  
  6. class DepthFirstSearchLargestArea
  7. {
  8.     // make our arrays static, so we can use them in method
  9.     static int[,] matrix =
  10.         {
  11.             {1,3,2,2,2,3},
  12.             {3,3,3,2,4,1},
  13.             {4,3,1,2,3,3},
  14.             {4,3,1,3,3,1},
  15.             {4,3,3,3,1,1},
  16.         };
  17.     static bool[,] checkedCells = new bool[matrix.GetLength(0), matrix.GetLength(1)];
  18.  
  19.  
  20.     static int DepthFirstSearch(int row, int col, int value)
  21.     {
  22.         // check if we have cell which is neighbour or we are on the bounds
  23.         if (row < 0 || col < 0 || row >= matrix.GetLength(0) || col >= matrix.GetLength(1))
  24.         {
  25.             return 0;
  26.         }
  27.  
  28.         // check if we already checked this cell
  29.         if (checkedCells[row, col] == true)
  30.         {
  31.             return  0;
  32.         }
  33.        
  34.         // check if the value is different from the searched one
  35.         if (matrix[row, col] != value)
  36.         {
  37.             return 0;
  38.         }
  39.  
  40.         // mark as read current cell
  41.         checkedCells[row, col] = true;
  42.  
  43.         // check neighbours of the cell, + 1 for this cell which already marked
  44.         return DepthFirstSearch(row, col + 1, value) + DepthFirstSearch(row, col - 1, value) +
  45.                DepthFirstSearch(row + 1, col, value) + DepthFirstSearch(row - 1, col, value) + 1;
  46.     }
  47.  
  48.     static void Main()
  49.     {
  50.         int result = -1;
  51.        
  52.         for (int row = 0; row < matrix.GetLength(0); row++)
  53.         {
  54.             for (int col = 0; col < matrix.GetLength(1); col++)
  55.             {
  56.                 result = Math.Max(result, DepthFirstSearch(row, col, matrix[row, col]));
  57.             }
  58.         }
  59.  
  60.         Console.WriteLine(result);
  61.     }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement