Students who want to check the real problems and solutions of other problems can go to check ：CCF-CSP True problem with complete solution
Question number ：202206-2 The title of the test question ： Treasure hunt ！ Great adventure ！ The time limit ：500ms Memory limit ：512.0MB Problem description ：
Summer vacation is coming . Unfortunately for a variety of reasons , Small P The original travel plan was cancelled . Disappointed little P I can only stay on West Island for a slightly monotonous holiday …… until ……
One day , Small P Got a mysterious treasure map .
On the island of sisieffer, there are n tree , The specific positions of these trees are recorded on a green map .
In short , The greening map of West Aifo island can be regarded as a map with a size of (L+1)×(L+1) Of 01 matrix A,
The lower left corner of the map （ coordinate (0,0)） And the upper right corner （ coordinate (L,L)） They correspond to each other A[0][0] and A[L][L].
among A[i][j]=1 Representation coordinates (i,j) There is a tree planted there ,A[i][j]=0 The coordinate (i,j) There are no trees .
In other words , matrix A There are and only n individual 1 It shows the island of West Eiffer n The exact location of the tree .
Legend has it that , The great adventurer Dunton's treasure is buried under a tree .
also , Dunton also cut a small piece from the green map of West West iver island , Make a treasure map to indicate its location .
say concretely , The treasure map can be regarded as a treasure map with a size of (S+1)×(S+1) Of 01 matrix B（S Far less than L）, Corresponding A Some part of .
Theoretically , Greening map A There is a coordinate in (x,y)（0≤x,y≤L−S） And the treasure map B The lower left corner (0,0) Corresponding , The meet ：
Yes B Any coordinate on (i,j)（0≤i,j≤S）, There are A[x+i][y+j]=B[i][j].
When the above conditions are met , We think of the treasure map B Corresponding to the greening map A The lower left corner in the middle is (x,y)、 The upper right corner is (x+S,y+S) Region .
actually , Considering that the treasure map depicts only a small area , Coordinates satisfying the above conditions (x,y) There may well be more than one .
Please refer to the greening map of West Eiffer island n The location of the tree , And small P The treasure map in your hand , Judge how many coordinates in the greening map meet the conditions .
Specially , The lower left corner of the treasure map must be a tree , namely A[x][y]=B[0][0]=1, It shows where the treasure is buried .
Reading data from standard input .
The first line of input contains three positive integers separated by spaces n、L and S, They represent the number of trees on the island of West Eiffer 、 The size of green map and treasure map .
Because the size of the greening map is too large , The input data contains only n The coordinates of a tree, not a complete map ; And then n Each row contains two integers separated by spaces x and y, Represents the coordinates of a tree , Satisfy 0≤x,y≤L And the same coordinate will not be repeated .
Last (S+1) Line input small P The complete treasure map in your hand , Among them the first i That's ok （0≤i≤S） Contains space delimited (S+1) individual 0 and 1, Express B[S−i][0]⋯B[S−i][S].
We need to pay attention to , The first input is B[S][0]⋯B[S][S] a line ,B[0][0]⋯B[0][S] Enter... At the end of a line .
Output to standard output .
Output an integer , Indicates how many coordinates in the green map can correspond to the lower left corner of the treasure map , That is to say, there may be buried treasures .
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
3
On the green map (0,0)、(1,1) and (2,2) There may be treasures buried in all three places .
5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
0
If you compare the lower left corner of the treasure map with the greening map (3,3) Corresponding to , The upper right corner of the treasure map will exceed the boundary of the green map , The correspondence is not successful .
40% The test data meet ：L≤50;
70% The test data meet ：L≤2000;
All test data meet ：n≤1000、L≤109 And S≤50.
The answer is not included in the actual test data 0 The use case .
The real question comes from ： Treasure hunt ！ Great adventure ！
Interested students can go in and practice
70 Sub topic solution ： Memory overrun
n, l, s = map(int,input().split())
points = [[i for i in map(int,input().split())] for j in range(n)]
money = [[i for i in map(int,input().split())] for j in range(s+1)]
data = [[0 for i in range(l+1)] for j in range(l+1)]
for point in points:
x = point[0]
y = point[1]
data[x][y] = 1
length = len(money)
if length%2 == 0:
for i in range(length//2):
for j in range(length):
money[i][j], money[s-i][j] = money[s-i][j], money[i][j]
else:
lake = length//2+1
for i in range(length//2):
if i == lake:
continue
for j in range(length):
money[i][j], money[s-i][j] = money[s-i][j], money[i][j]
time = 0
for point in points:
x = point[0]
y = point[1]
q = 0
for i in range(s+1):
if x+i > l:
q = 1
break
if q == 1:
break
for j in range(s+1):
if y+j > l:
q = 1
break
if money[i][j] == data[x+i][y+j]:
continue
else:
q = 1
break
if q == 0:
time += 1
print(time)Running results ：
ccf-csp Practice column
https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482
https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482
