There is thought to be a mosaic in a rectangle H
composed by MxN cells situated in M rows and N columns. The original of this
hypothetical mosaic is in another rectangle O composed by PxQ cells situated in
P rows and Q columns. All the cells in both rectangles are white or black
colored. (1<M,N,P,Q<=100)
All black cells of the rectangle O are part of the
mosaic, whereas a white cell is considered to be part of the mosaic only if it
is between at least two black cells not necessary neighbor in one of the
directions: horizontal, vertical, diagonal.
Given the original mosaic situated in the rectangle
O, You have to write a program, which will discover if there is a mosaic
identical with this in the rectangle H.
If so, in the output file You have to write the ‘YES’ in the first row, and two integers that represent the coordinates of the first cell of the mosaic in the second row. The first cell of the mosaic is considered the cell that has the smallest row coordinate, and for this has the smallest column coordinate.
The input text file c:\day1\problem1\mosaic.in has in the first line two integers P, Q
that are the dimensions of the rectangle where is the original mosaic O.
In the following P lines there are Q integers in each line, which values are 0 or 1. The value 0 stands for a white cell, whereas a value 1 stands for a black cell. The integers are separated by a space.
In the following line are two integers M, N that are the dimensions of the rectangle H where a copy of the mosaic is supposed to be.
After follow M lines with N integers 0, 1 each.
The output text file c:\day1\problem1\mosaic.out has two lines.
In the first line will be a ‘YES’ or ‘NO’ according
the fact that there is a copy of the mosaic in the rectangle H or not.
If yes, then will be a second line with two integers
separated by a space. These integers show the coordinates of the first cell of
the copy of the mosaic.
Example 1
Mosaic.in
7 8
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 1 1 1 1 0 1
0 1 1 0 0 1 1 0
0 0 1 1 1 1 0 1
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
8 9
1 1 0 0 1 1 1 1 0
0 0 0 0 0 0 1 1 1
0 0 0 1 1 0 0 1 0
1 1 1 1 1 1 0 1 0
1 1 1 0 0 1 1 0 1
1 0 1 1 1 1 0 1 0
1 1 0 1 1 0 0 0 1
1 1 0 0 0 0 1 1 0
mosaic.out
YES
3 4
Example 2
mosaic.in
3 3
0 1 0
1 0 1
0 1 0
3 3
0 1 0
1 1 1
0 1 0
mosaic.out
NO
Time limit per test 1 sec.