Flip AB

3

4 votes
Brute Force, Greedy Algorithms, Basics of Greedy Algorithms, Algorithms
Problem

Given two grids, both with \(n\) rows and \(m\) columns, and cells containing either the letter 'A' or the letter 'B'. Determine if it is possible to use either of the subsequent operations any number of times, including \(0\), to transform the first grid, \(grid_{1}\), to the second grid, \(grid_{2}\):

  • ROW FLIP: In this operation, you choose a row in \(grid_{1}\) and flip all the characters in the chosen row.
  • COLUMN FLIP: In this operation, you choose a column in \(grid_{1}\) and flip all the characters in the chosen column.

A flip changes the letter 'A' to letter 'B', and vice-versa.

Your program should output "YES" (without quotes) if it is possible to convert \(grid_{1}\) to \(grid_{2}\), and "NO" (without quotes) otherwise. 

NOTE: You can perform the operations on \(grid_{1}\) only. 

INPUT FORMAT

The first line contains an integer, \(t\) \((1 <= t <= 10^3)\) - denoting the number of test cases. 

The first line of each test case contains two integers \(n\) (\(1 <= n <= 10^3\)), and \(m\) \((1 <= m <= 10^3)\) - denoting the number of rows, and columns both grids have. 

The following \(n\) lines of each test case contain a string of length \(m\) having characters as either 'A' or 'B' - denoting the characters in \(grid_{1}\).

The final \(n\) lines of each test case contain a string of length \(m\) having characters as either 'A' or 'B' - denoting the characters in \(grid_{2}\)

It is guaranteed that the sum of \(nm\) across all test cases doesn't exceed \(10^6\).

OUTPUT FORMAT

Output a string "YES" (without quotes) if it is possible to convert \(grid_{1}\) to \(grid_{2}\), and a string "NO" (without quotes) otherwise. 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In the only test case given sample you can transform \(grid_{1}\) to \(grid_{2}\) as follows: 

Editor Image

?