The simplest way to find a known pattern is to try every position and measure the difference.
What to build
A program that computes the sum-of-squared-differences map and the best match.
Requirements
- The score at (r, c) is the sum over the template of (img[r + i][c + j] − t[i][j])².
- Print the score map, one line per row of positions, then
best at row R, column Cfor the smallest score (first in reading order on ties).
Input
Line 1: H and W. Then H rows. Then h and w. Then h template rows.
Output
The score rows and the best line.
Constraints
1 ≤ h ≤ H ≤ 40; 1 ≤ w ≤ W ≤ 40.
Example
Input:
3 3
1 2 3
4 5 6
7 8 9
2 2
5 6
8 9
Output:
64 36
4 0
best at row 1, column 1
Why it works
Squared differences are 0 only where window and template agree exactly, so the smallest score marks the position that differs least from the template.
Examples
Example 1 · Input
3 3 1 2 3 4 5 6 7 8 9 2 2 5 6 8 9
Expected output
64 36 4 0 best at row 1, column 1
Example 2 · Input
2 4 0 9 0 9 9 0 9 0 1 2 9 0
Expected output
162 0 162 0 162 0 best at row 0, column 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The template fits at (H − h + 1) × (W − w + 1) top-left positions.
Hint 2
Keep the first position with the smallest score when scanning row by row.
Solution
Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
th, tw = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(th)]
best = None
for r in range(h - th + 1):
row = []
for c in range(w - tw + 1):
s = sum((img[r + i][c + j] - t[i][j]) ** 2 for i in range(th) for j in range(tw))
row.append(s)
if best is None or s < best[0]:
best = (s, r, c)
print(" ".join(map(str, row)))
print(f"best at row {best[1]}, column {best[2]}")