Question

Anyone knows how to write a code to solve the following problem?

A idea I have is to map the bottom square ontop the top square starting from top left to bottom right, but m unsure if thats achievable
Language preferably in C++, java and python is also accepted

Answer 1

import re

def solve(n, painting, k, stamp):

# define a function to check if the stamp is inside the painting

def is_in_painting(i, j):

return i >= 0 and j >= 0 and i + k <= n and j + k <= n

# define a function to check if the stamp matches the painting

def matches_painting(i, j):

for x in range(k):

for y in range(k):

if painting[i+x][j+y] != stamp[x][y]:

return False

return True

# try to match the stamp in each position

for i in range(n):

for j in range(n):

if is_in_painting(i, j) and matches_painting(i, j):

return True

return False

# read in the input

input_string = """4

2

**

.*

1

*

3

.**

.**

***

2

.*

**

3

...

.*.

..."""

# parse the input string

input_lines = input_string.strip().split('\\')

n = int(input_lines.pop(0))

painting = [list(line) for line in input_lines[:n]]

input_lines = input_lines[n:]

k = int(input_lines.pop(0))

stamp = [list(line) for line in input_lines[:k]]

# solve the problem

if solve(n, painting, k, stamp):

print("YES")

else:

print("NO")

Step-by-step explanation: