Flip Grid

3.2

4 votes
Implementation, Graphs, Algorithms, Brute Force, Breadth-first search
Problem

Alice was given two 4 x 4 binary grids, A and B. She wants to convert grid A to B. She can perform any of the following operations any number of times on grid A (she can't modify B): 

  1. Rotate grid A clockwise by 90 degrees. 
  2. Flip a row in grid A i.e. change all 0's in the chosen row to 1's, and 1's to 0's. 
  3. Flip a column in grid A i.e. change all 0's in the chosen column to 1's, and 1's to 0's. 

Output the minimum number of moves that Alice needs to convert A to B, or 1 if it is impossible to make both grids equal. 

 

INPUT FORMAT

The first 4 lines of the input each contain a string of length 4 - denoting the rows in grid A, each character in the string is either 0 or 1

The next line is an empty line. 

The remaining 4 lines of the input each contain a string of length 4 - denoting the rows in grid B, each character in the string is either 0 or 1.

 

OUTPUT FORMAT 

The first and only line of the output should contain the minimum number of operations Alice needs to convert grid A to B, or 1 if it's impossible to do so, using the operations in the statement. 

Sample Input
0001
1000
0001
1000

0101
0000
0000
0101
Sample Output
2
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

One possible sequence of operations that converts the first grid to the second grid is: 

Flipping A clockwise, and then flipping the first row of A.

You cannot convert A to B in less than 2 operations. 

Editor Image

?