#P3600. Subimage Recognition
Subimage Recognition
Description
An image A is said to be a subimage of another image B if it is possible to remove some rows and/or columns of pixels from B so that the resulting image is identical to A. Figure 6 illustrates an example. Image A, shown in Figure 6(a), is a subimage of image B, shown in Figure 6(b), because the image resulting from the removal of the middle row and column of pixels from B is identical to A.
(a) Image A | (b) Image B |
Figure 6: An example of a subimage
Given two black-and-white images A and B, determine whether A is a subimage of B.
Input
The input contains a single test case. The first line contains two integers r and c (1 ≤ r, c ≤ 20), the dimensions of A. The following r lines, each containing a string of length c, give an r × c 0-1 matrix representing the pixels of A. The next line contains two integers R and C (r ≤ R ≤ 20; c ≤ C ≤ 20), the dimensions of B. The following R lines, each containing a string of length C, give an R × C 0-1 matrix representing the pixels of B. A 0 indicates a white pixel; a 1 indicates a black pixel.
Output
If A is a subimage of B, print “Yes”; otherwise, print “No”.
2 2
11
10
3 3
101
000
100
Yes
Source
PKU Campus 2008 (POJ Founder Monthly Contest – 2008.05.10), frkstyc