Last Updated: 26 Dec, 2020
Grid Overlap
Easy
Asked in companies
You are given two binary grids ‘MAT1’ and ‘MAT2’ of size N x N each. Both grids either have 0 or 1 written in each cell.
You can perform four types of operations to MAT1-
• Right Shift
• Left Shift
• Up Shift
• Down Shift
For eg:
Let the grid MAT1 be-
After one right shift, it will look like-
After one left shift, it will look like-
After one up shift, it will look like-
After one down shift, it will look like-
You can perform any of the above operations in any order, any number of times(possibly zero) to MAT1.
Overlap of two grids is defined as the number of cells which have 1 written in it, in both the grids. Your task is to find the maximum possible overlap between ‘MAT1’ and ‘MAT2’ after applying some operations to ‘MAT1’.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains one integer ‘N’ denoting the number of rows and columns in the grid ‘MAT1’ and ‘MAT2’.
The next ‘N’ lines of each test case contain ‘N’ space-separated integers each representing the rows of ‘MAT1’
The next ‘N’ lines of each test case contain ‘N’ space-separated integers each representing the rows of ‘MAT2’.
Output Format :
For each test case, print the maximum possible overlap.
The output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 30
0 <= MAT1[i][j] <= 1
0 <= MAT2[i][j] <= 1
Time Limit: 1 sec.
Approaches
For any cell A of MAT1 which has one and cell B of MAT2 which has one we can define linear transformation L as - (difference of X - coordinates of A and B, difference of Y - coordinates of A and B). The cells which come under the same overlapping zone will have the same value of L.
The algorithm will be-
- We will store all the cells which have ones in ‘MAT1’ in an array/list first.
- We will store all the cells which have ones in ‘MAT2’ in an array/list second.
- We will also declare a hashMap ‘frequency’, which stores the count of the linear transformation.
- For each element in the first, we will find the value of L for each element of the second using two nested loops. Let this value be P.
- We will increment ‘frequency[P]’ by 1.
- The maximum count of an element in the hashmap ‘frequency’ will be our answer.
Let there be ‘x’ right shifts and ‘y’ up shifts of MAT1. We can iterate over x and y to find the final configuration of MAT1 and calculate the value of overlap. All possible left and down shifts of MAT1 can be equivalently represented by right and up shifts of MAT2.
The algorithm will be-
- We will iterate over x and y with the help of two nested loops.
- For some possible right shifts and up shifts we will find the final configuration of MAT1.
- We will find the value of overlap for each configuration of MAT1.
- We will again iterate over x and y with the help of two nested loops for MAT2.
- For some possible right shifts and up shifts we will find the final configuration of MAT2.
- We will find the value of overlap for each configuration of MAT2.
- The maximum value of overlap encountered will be our answer.