We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. The Grid Search
  5. Discussions

The Grid Search

Sort by

recency

|

903 Discussions

|

  • 0xmillennium
     + 0 comments

    Here's a One Line Python Magic

    def gridSearch(G, P):
    return "YES" if re.search(f".{{{len(G[0]) - len(P[0]) + 1}}}".join(P), " ".join(G)) else "NO"

  • mohammed_abrar_1
     + 0 comments

    import java.io.; import java.util.; import java.util.stream.*;

    class Result {

    public static String gridSearch(List<String> G, List<String> P) {
    int R = G.size();
    int C = G.get(0).length();
    int r = P.size();
    int c = P.get(0).length();

    for (int i = 0; i <= R - r; i++) {
        for (int j = 0; j <= C - c; j++) {
            boolean found = true;
            for (int k = 0; k < r; k++) {
                if (!G.get(i + k).substring(j, j + c).equals(P.get(k))) {
                    found = false;
                    break;
                }
            }
            if (found) return "YES";
        }
    }
    return "NO";
}

    }

    public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

    for (int tItr = 0; tItr < t; tItr++) {
        String[] firstMultipleInput = bufferedReader.readLine().trim().split(" ");
        int R = Integer.parseInt(firstMultipleInput[0]);
        int C = Integer.parseInt(firstMultipleInput[1]);

        List<String> G = new ArrayList<>();
        for (int i = 0; i < R; i++) {
            G.add(bufferedReader.readLine());
        }

        String[] secondMultipleInput = bufferedReader.readLine().trim().split(" ");
        int r = Integer.parseInt(secondMultipleInput[0]);
        int c = Integer.parseInt(secondMultipleInput[1]);

        List<String> P = new ArrayList<>();
        for (int i = 0; i < r; i++) {
            P.add(bufferedReader.readLine());
        }

        String result = Result.gridSearch(G, P);
        bufferedWriter.write(result);
        bufferedWriter.newLine();
    }

    bufferedReader.close();
    bufferedWriter.close();
}

    }

  • dangtri113
     + 0 comments

    Here my solution

    function gridSearch($G, $P) {
    // Write your code here
    $xG = count($G);
    $yG = strlen($G[0]);
    $xP = count($P);
    $yP = strlen($P[0]);
    
    for($x=0; $x<=$xG-$xP; $x++) {
        for ($y=0; $y<=$yG-$yP; $y++) {
            $matchLines = 0;
            for($i=0; $i<$xP; $i++) {
                if(substr($G[$i+$x], $y, $yP) !== $P[$i]) break;
                $matchLines++;
            }
            
            if($matchLines === $xP) return "YES";
        }
    }
    
    return "NO";
}

  • raghavendragk
     + 0 comments

    Tip for C++ implementation: Use pass by reference for passing the grids. This will help clear the largest input, test case 5.

  • saminazubair93
     + 0 comments

    Here is my solution in PHP

        $prows = count($P);
    $grows = count($G);
    $firstRow = array();
    $firstIndex = array();
    
    $result = 'NO';
    for ($i=0; $i <=$grows-($prows-1) ; $i++) { 
        $rowIndex = array();
        $offset = 0;
        while(($str = strpos($G[$i], $P[0],$offset))!== false)
        {
            $rowIndex[] = $str;
            $offset = $str+1;

        }
        $firstRow[$i] = $rowIndex;
    }

 
     foreach ($firstRow as $key => $value) {
         // code...
        if($result == 'YES')
        {
            break;
        }
        if($grows - ($key) >= $prows)
        {
            foreach ($value as $key1 => $value1) {
                 $keyIndex =  $value1;
                 $newKey = 0;
                 $lastIndex = $key+$prows-1;
                
                      for ($i=$key+1; $i <($key+$prows) ; $i++) { 
                         
                      $newKey+=1;
                      
                      $str = strpos($G[$i], $P[$newKey],$value1);
                     
                if ($str !== false && $str == $keyIndex) {
                        if($i == $lastIndex)
                         {
                           $result = 'YES';
                            break;
                         }
                }
               else
               {
                break;
               }

             
           }
           
            }
         
         
   
        }
        else
        {
            continue;
        }
     }    
 return $result;