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

  • JsFoxy
     + 4 comments

    Here is my solution in Javascript using RegEx. I pass all test cases and times range from 0.06s up to 0.15s

    function main() {
    var t = parseInt(readLine());
    for(var a0 = 0; a0 < t; a0++){
        var R_temp = readLine().split(' ');
        var R = parseInt(R_temp[0]);
        var C = parseInt(R_temp[1]);
        var G = [];
        for(var G_i = 0; G_i < R; G_i++){
           G[G_i] = readLine();
        }
        var r_temp = readLine().split(' ');
        var r = parseInt(r_temp[0]);
        var c = parseInt(r_temp[1]);
        var P = [];
        for(var P_i = 0; P_i < r; P_i++){
           P[P_i] = readLine();
        }
    	
        
        // -------------- Code below this point -----------
        var patt_len = P.length;
        var offset   = (G[0].length - P[0].length)+1;
        var pattern  = '';
        var regex;
        var result;
        var i;
        var str = '';

     	// Simply concatenate grid using . as separaor
        // make sure u use some kind of separator or
        // it won't work, you can use anything but
        // numbers here as separator
        str = G.join('.');

        // Here I build RegEx pattern
        for(i = 0; i < patt_len; i++)
        {
            if(i !== (patt_len - 1)){
                pattern += '(' + P[i] + ').{' + offset + '}';
            } else {
                pattern += '(' + P[i] + ')';
            }
        }
		
        // And in end we run it on our strig 
        // and see if we have match or not
        regex = new RegExp(pattern);
        result = str.match(regex);
        console.log(result !== null ? 'YES' : 'NO');
    }

}

    So idea was to get grid array in one string, and then use pattern array to build RegEx expression and run it on string. So for example let's let's take one of default inputs:

    10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530

    After we concatenate our grid will look like:

    // note that u can use any simbol to concatenate string
// just make sure it's not a number :)
7283455864.6731158619.8988242643.3830589324.2229505813.5633845374.6473530293.7053106601.0834282956.4607924137

    And our pattern will look like this:

    //note that "." in this regex it's not actual dot we used
// to concatenate string. The {7} part we got by calculating
// how much apart our patten needs to be in a string, we simply
// use our (grid length - pattern length) + 1, we need this +1
// to count in our concatenate simbol, in my case dot.
/(9505).{7}(3845).{7}(3530)/g