Problem:


Score : 200 points

Problem Statement

You are given an image A composed of N rows and N columns of pixels, and a template image B composed of M rows and M columns of pixels.

A pixel is the smallest element of an image, and in this problem it is a square of size 1×1.

Also, the given images are binary images, and the color of each pixel is either white or black.  

In the input, every pixel is represented by a character: . corresponds to a white pixel, and # corresponds to a black pixel.

The image A is given as N strings A_1,...,A_N.

The j-th character in the string A_i corresponds to the pixel at the i-th row and j-th column of the image A (1≦i,j≦N).

Similarly, the template image B is given as M strings B_1,...,B_M.

The j-th character in the string B_i corresponds to the pixel at the i-th row and j-th column of the template image B (1≦i,j≦M).  

Determine whether the template image B is contained in the image A when only parallel shifts can be applied to the images.  

Constraints

1≦M≦N≦50 

A_i is a string of length N consisting of # and ..

B_i is a string of length M consisting of # and ..

Input

The input is given from Standard Input in the following format:

N M
A_1
A_2
:  
A_N
B_1
B_2
:  
B_M

Output

Print Yes if the template image B is contained in the image A. Print No otherwise.

Sample Input 1

3 2
#.#
.#.
#.#
#.
.#

Sample Output 1

Yes

The template image B is identical to the upper-left 2 × 2 subimage and the lower-right 2 × 2 subimage of A. Thus, the output should be Yes.

Sample Input 2

4 1
....
....
....
....
#

Sample Output 2

No

The template image B, composed of a black pixel, is not contained in the image A composed of white pixels.



Sample input:
3 2
#.#
.#.
#.#
#.
.#


Sample output:
Yes

Submission status: Runtime Error

Solution code:
n,m = map(int, raw_input().split())
np=[]
mp=[]
for i in xrange(0, n):
  np.append(raw_input())
for i in xrange(0, m):
  mp.append(raw_input())

for i in xrange(0,n-m+1):
  for j in xrange(0, n-m+1):
    flag = True
    for x in xrange(0, m):
      for y in xrange(0, m):
        if mp[x][y] != np[i+x][j+y]:
          flag = False
          break
      if flag == False:
        break
    if flag:
      print "Yes"
      return
print "No"

Submission status: Runtime Error

Solution code:
np=[]
mp=[]
for i in xrange(0, n):
  np.append(raw_input())
for i in xrange(0, m):
  mp.append(raw_input())

for i in xrange(0,n-m):
  for j in xrange(0, n-m):
    flag = True
    for l in xrange(0, m):
      for m in xrange(0, n):
        if mp[l][m] != np[i][j]:
          flag = False
          break
      if !flag:
        break

if flag:
  print "Yes"
else:
  print "No"

Submission status: Runtime Error

Solution code:
N, M = input().split()
A=[]
for i in range(0,N):
    A.append(input())
B=[]
for j in range(0,M):
    B.append(input())

ref_tuple = zip(range(0,N-M+1),range(0,N-M+1))
t=False
for ref_row_a, ref_col_a in ref_tuple:
    for row_b, col_b in zip(range(0,M),range(0,M)):
        if not A[ref_row_a+row_b][ref_col_a+col_b]==B[row_b][col_b]:
            break
        if (row_b, col_b)==(M-1,M-1):
            t=True
            break
    if t:
        break

if t:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
#include <string>
#include <iostream>

using namespace std;

const int nmax = 50;
const int mmax = 50;
char N_sq[nmax][nmax], M_sq[mmax][mmax];


bool judge_match(int x, int y, int M){
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			if(N_sq[y+i][x+j] != M_sq[y+i][x+j]) return false;
		}
	}
	return true;
}


int main(void){
	int N,M;

	cin >> N >> M;
	bool exist = false;

	for(int y=0;y < N;y++){
		for(int x;x < N;x++){
			cin >> N_sq[y][x];
		}
	}

	for(int y=0;y < M;y++){
		for(int x;x < M;x++){
			cin >> M_sq[y][x];
		}
	}

	for(int y=0;y <= N - M;y++){
		for(int x=0;x <= N - M;x++){
			if(judge_match(x, y, M)) exist=true;
		}
	}

	if(exist)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;

}

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
checker = True

n, m = map(int, raw_input().split())
N = []
M = []
counter = 0
ans = "No"
flag = 0
while checker:
    tmp = raw_input()
    if counter < n:
        N.append(tmp)
    else:
        M.append(tmp)
    counter += 1
    if counter == n + m:
        break

if M[0].find(N[0]) > -1:
    flag = 1
    start = M[0].find(N[0]) #開始文字列index
    for st in M:
        for stm in N:
            ch = st.find(stm)
            if ch == start:
            else:
                flag = 0
                
ans = "Yes" if flag == 1 else "No"
# 出力
print ans

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,raw_input().split())
a = [[0 for i in range(n)] for j in range(n)]
b = [[0 for i in range(m)] for j in range(m)]
z = []
for i in range(n):
    at = list(raw_input())
    a[i] = at
for i in range(m):
    at = list(raw_input())
    b[i] = at
if n == m:
        if a == b:
            print "Yes"
            sys.exit(0)
        else:
            print "No"
            sys.exit(0)
temp = [[0 for i in range(m)] for j in range(m)]
for i in range(n-m+1):
    for j in range(n-m+1):
        for k in range(m):
            temp[k] = a[i+k][j:j+m]
        if temp == b:
            print "Yes"
            sys.exit(0)
        else:
            temp = [[0 for i in range(m)] for j in range(m)]
print "No"

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(str(input()))
b = []
for i in range(m):
    b.append(str(input()))

f = [0]*m
count = 0
for j in range(m):
    f[j] = a[j].find(b[j])

while -1 in f: f.remove(-1)
if len(f) == 0:
    print('No')
else:
    flag = 1
    for i in range(len(f)):
        if (b[f[i]] in a[f[i]]) == False:
            flag =0
    if flag == 1:
        print('Yes')
    else:
        print('No')

Submission status: Runtime Error

Solution code:
n,m = map(int, raw_input().split())
n_list = [] #row major format
m_list = []
for i in range(0, n):
	n_list.append(raw_input())

for x in range(0, m):
	m_list.append(raw_input())

def match_first_rows(n_start):
	result = (-1,-1)
	first_m = m_list[0] # first row
	for x in range(n_start, n):
		n_row = n_list[x]
		if first_m in n_row: # substring matching of first m_row
			j = n_row.index(first_m)
			return (x, j)
	return (-1,-1) #return -1,-1 if none found

# given the leftmost corner of matching in matrix n, start matching each row to see if there is a potential match
# only guranteed first row match
def begin_matching(i,j):
	nx_start = i
	ny_start = j
	for x in range(0,m):
		n_row_string = n_list[nx_start+x]
		n_string = n_row_string[j:j+m] # align window
		m_string = m_list[x]
		if n_string!=m_string:
			return False
	return True

def find_m():

	found_m = False
	counter = 0
	while(counter<n and not(found_m)):

		i,j = match_first_rows(counter)
		if i==-1: 
			#goes through entirety, not returning things at all
			print("No")
			found_m = True
		# found a potential starting point
		else:
			result = begin_matching(i,j)
			if result:
				print("Yes")
				found_m = True
			else:
				#do it again, but one row lower
				counter +=1 

find_m()

Submission status: Runtime Error

Solution code:
data = raw_input()

n,m = map(int,data.split(" "))

data = []

for x in range(n):
  data.append(raw_input())

temp = []

for x in range(m):
  temp.append(raw_input())

for x in range(n):
  for y in range(n):
    if temp[0] == data[x][y:y+m]:
      flag = 1
      pos = y
      for xx in range(x+1,x+m):
        if temp[xx - x] != data[xx][pos:pos+m]:
          flag = 0
          break
      if flag == 1:
        print "Yes"
        exit(0)

print "No"

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(str(input()))
b = []
for i in range(m):
    b.append(str(input()))

f = [0]*m
count = 0
for j in range(m):
    f[j] = a[j].find(b[j])

while -1 in f: f.remove(-1)
if len(f) == 0:
    print('No')
else:
    flag = 1
    for i in range(len(f)):
        if  b[f[i]] in a[f[i]]:
            pass
        else:
            flag =0
    if flag == 1:
        print('Yes')
    else:
        print('No')

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
temp = input().split()
N = int(temp[0])
M = int(temp[1])
A = []
B = []
check = False
def change(n):
  if(n=='#'):
    return True;
  return False;

for i in range(N):
  temp = input()
  A.append(list(map(change, temp)))
for i in range(M):
  temp = input()
  B.append(list(map(change, temp)))
A = np.array(A)
B = np.array(B)

for i in range(N-M+1):
  for j in range(N-M+1):
    if (B== A[i:M+j, i:M+j]).all():
      check = True
      break
  if check:
    break

if check:
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
A, B = [], []

for i in range(n):
    A.append(input())

for i in range(m):
    B.append(input())

def is_contain(i, b_pos):
    containing = True
    for a_i in range(i+1, i+m):
        if A[a_i][b_pos:(b_pos+len(B))] != B[a_i]:
            containing = False
    return containing

if n < m or len(A) < len(B):
    print("No")
    exit()

for i in range(n - m + 1):
    lineA = A[i]
    lineB = B[i%m]
    lineB_pos = lineA.find(lineB)
    if lineB_pos >= 0:
        if is_contain(i, lineB_pos):
            print("Yes")
            exit()

print("No")

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
temp = input().split()
N = int(temp[0])
M = int(temp[1])
A = []
B = []
def change(n):
  if(n=='#'):
    return True;
  return False;

for i in range(N):
  temp = input()
  A.append(list(map(change, temp)))
for i in range(M):
  temp = input()
  B.append(list(map(change, temp)))
A = np.array(A)
B = np.array(B)

for i in range(N-M+1):
  for j in range(N-M+1):
    if (B== A[i:M+j, i:M+j]).all():
      print("Yes")
      sys.exit()

print("No")

Submission status: Runtime Error

Solution code:
n,m = map(int, raw_input().split())
n_list = [] #row major format
m_list = []
for i in range(0, n):
	n_list.append(raw_input())

for x in range(0, m):
	m_list.append(raw_input())

def match_first_rows(n_start):
	result = (-1,-1)
	first_m = m_list[0] # first row
	for x in range(n_start, n):
		n_row = n_list[x]
		if first_m in n_row: # substring matching of first m_row
			j = n_row.index(first_m)
			return (x, j)
	return (-1,-1) #return -1,-1 if none found

# given the leftmost corner of matching in matrix n, start matching each row to see if there is a potential match
# only guranteed first row match
def begin_matching(i,j):
	nx_start = i
	ny_start = j
	for x in range(0,m):
		n_row_string = n_list[nx_start+x]
		n_string = n_row_string[j:j+m] # align window
		m_string = m_list[x]
		if n_string!=m_string:
			return False
	return True

def find_m():

	found_m = False
	counter = 0
	while(counter<n and not(found_m)):

		i,j = match_first_rows(counter)
		if i==-1: 
			#goes through entirety, not returning things at all
			print("No")
			found_m = True
		# found a potential starting point
		else:
			result = begin_matching(i,j)
			if result:
				print("Yes")
				found_m = True
			else:
				#do it again, but one row lower
				counter +=1 

find_m()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
N = int(input())
M = int(input())
A = []
B = []
def change(n):
  if(n=='#'):
    return True;
  return False;

for i in range(N):
  temp = input()
  A.append(list(map(change, temp)))
for i in range(M):
  temp = input()
  B.append(list(map(change, temp)))
A = np.array(A)
B = np.array(B)

for i in range(N-M+1):
  for j in range(N-M+1):
    if (B== A[i:M+j, i:M+j]).all():
      print("Yes")
      sys.exit()

print("No")

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())

A = []
B = []
for i in range(N):
    A.append(input())
for i in range(M):
    B.append(input())


for i in range(N-M):
    x = A[i].find(B[0])
    if x != -1:
        result = True
        break
    result = False

for j in range(1,M):
    if (j >= M or j >= N ):
        result = False
        break
    idx = A[j][x:].find(B[j])
    if idx != x:
        result = False
        break

if result == True:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())

A = []
B = []
for i in range(N):
    A.append(input())
for i in range(M):
    B.append(input())


for i in range(N-M):
    x = A[i].find(B[0])
    if x != -1:
        result = True
        break
    result = False

for j in range(1,M):
    idx = A[j][x:].find(B[j])
    if idx != x:
        result = False
        break

if result == True:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
def check(y,x):
    if 0<=y<=n-1 and 0<=x<=n-1:
        return True
    return False
n,m=map(int,raw_input().split())
a=[raw_input() for _ in xrange(n)]
b=[raw_input() for _ in xrange(m)]
for i in xrange(m):
    for j in xrange(m):
        cnt=0
        for k in range(i,i+m):
            for l in xrange(j,j+m):
                if check(k,l):
                    if a[k][l]==b[k][l]:
                        cnt+=1
        if cnt==m*m:
            print("Yes")
            exit()
print("No")