Flip AB
Practice
3 (4 votes)
Brute force
Greedy algorithms
Basics of greedy algorithms
Algorithms
Problem
55% Success 458 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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. 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
3 votes
Tags:
Basics of Greedy AlgorithmsAlgorithmsGreedy Algorithms
Points:30
5 votes
Tags:
Greedy AlgorithmsAlgorithmsBasics of Greedy AlgorithmsGreedy algorithm
Points:30
7 votes
Tags:
Greedy AlgorithmsBasics of Greedy AlgorithmsAlgorithms