X Total Shapes

X Total Shapes

  August 02, 2017    

---

Problem :

Given N * M string array of O's and X's
Return the number of 'X' total shapes. 'X' shape consists of one or more adjacent X's (diagonals not included).

SOlution:

Just check with adjacent vertex having X and unvisited ,and follow DFS/BFS for that vertices.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     //static
     public static void DFS(boolean visited[][],char arr[][],int i,int j,int n,int k)
     {
         if(arr[i][j]=='X' && !visited[i][j])
         {
             visited[i][j]=true;
            if(i+1<n) DFS(visited,arr,i+1,j,n,k);
            if(i-1>=0) DFS(visited,arr,i-1,j,n,k);
             if(j+1<k)DFS(visited,arr,i,j+1,n,k);
            if(j-1>=0) DFS(visited,arr,i,j-1,n,k);
         }
         else
         return;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int l=ab.nextInt();
while(l-->0)
{
   int count=0;
   int n=ab.nextInt();
   int k=ab.nextInt();
   char arr[][]=new char[n][k];
   for(int i=0;i<n;i++)
   {
       String tm=new String(ab.next());
       for(int j=0;j<k;j++)
   arr[i][j]=tm.charAt(j);
  // ab.next();
}
boolean visited[][]=new boolean[n][k];

boolean flag;
for(int i=0;i<n;i++)
   {
       for(int j=0;j<k;j++)
       {
            if(arr[i][j]=='X' && !visited[i][j])
            {DFS(visited,arr,i,j,n,k);
                count++;
            }
       }}


/* for(int i=0;i<n;i++)
   {for(int j=0;j<k;j++)
   System.out.print(arr[i][j]);
   //ab.next();
   System.out.println();
} */
System.out.println(count);
}

}
}