Dinoscan
Time limit2sMemory limit512 MB
Given two binary scans with aligned rows, decide whether shifting the right scan horizontally lets the 1s tile one solid rectangle with no gaps or overlaps.
- Level
Medium5 of 10
- Topics
- Implementation, Brute force, Matrix, Simulation
- Solved
- No attempts yet
Problem
Sarah Tops is a paleontologist who reconstructs dinosaur skeletons. One problem she faces is deciding whether two bones fit together. She has scanned every bone in her collection, so instead of physically trying to join bones she plans to read the scans and work out which bones connect. The two pictures on the left below are scans of the ends of two different bones.
In a scan, a 1 marks bone and a 0 marks empty space. Two bones mesh if the two scans can be put together so that the 1s fill one solid rectangle with no gap and no overlap. Scan 1 meshes with Scan 2, as the picture on the right shows, but Scan 1 meshes with neither Scan 3 nor Scan 4 below.
The two scans keep their rows aligned and slide only sideways. Shift the right hand scan by a whole number of columns. The scans mesh if the cells holding a 1 then fill one rectangle completely and no cell holds a 1 from both scans. A column made only of 0s may sit outside that rectangle. The first column of the left hand scan and the last column of the right hand scan are all 1s, so the rectangle starts at the first column of the left hand scan and ends at the last column of the right hand scan.
Input
The first line holds three positive integers , and . Here is the number of rows in both scans, is the number of columns in the left hand scan, and is the number of columns in the right hand scan.
The next lines hold characters each and form the left hand scan. The lines after those hold characters each and form the right hand scan. Every character of a scan is 0 or 1.
The largest value of , and is 20. In every input the first column of the left hand scan and the last column of the right hand scan hold only 1s.
Output
Print Yes if the two scans mesh, and No otherwise. If even one cell holding a 1 falls outside the rectangle, the scans do not mesh.




