Wednesday 18 November 2015

Java 2D array Grid Search

Java 2D array:   Search sub array inside a array'

Note:
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two tab-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.

Solution:


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static void main(String[] args)
{
   /--------------------Input------ see Note--------------------
    Scanner scan = new Scanner(System.in);
    int steps = Integer.parseInt(scan.nextLine());
    while(steps >0){
        int sr = scan.nextInt();
        int sc = scan.nextInt();
        boolean found = false;
        scan.nextLine();
        int[][] m1 = new int[sr][sc];
        for(int i=0;i<sr;i++){
            String row = scan.nextLine();
            for(int j=0;j<sc;j++){
                m1[i][j] = (int)(row.charAt(j) );
            }

        }
/--------------------Input End--------------------------
        int fr = scan.nextInt();
        int fc = scan.nextInt();

        scan.nextLine();
        int[][] m2 = new int[fr][fc];

        for(int i=0;i<fr;i++){
            String row = scan.nextLine();

            for(int j=0;j<fc;j++){
                m2[i][j] = (int)(row.charAt(j) );
            }

        }

        outLoop:
        for(int i=0;i<sr;i++){
            for(int j=0;j<sc;j++){
                if(m1[i][j]==m2[0][0]){
                   if(isMatrix(m1,m2,fr,fc,i,j) ){
                       found = true; 
                       break outLoop;
                   } else{
                       found = false;
                   }
                }
            }
        }

       String r = (found==true)?"YES":"NO"; 
       System.out.println(r);

        steps--;
    }
}
public static boolean isMatrix(int[][] m1, int[][] m2, int fr, int fc, int i, int j){
    boolean found = true;
    for(int a=0;a<fr;a++){
        for(int b=0;b<fc;b++){
            try{
                if(m2[a][b]!=m1[i+a][j+b]){                       
                    return false;
                }
            }
            catch(Exception e){
               return false;
            }

        }
    }
     return true;
}
}

No comments:

Post a Comment