python解CCF-CSP真題《202206-2—尋寶！大冒險！》

想查看其他題的真題及題解的同學可以前往查看：CCF-CSP真題附題解大全

題目背景

暑假要到了。可惜由於種種原因，小 P 原本的出游計劃取消。失望的小 P 只能留在西西艾弗島上度過一個略顯單調的假期……直到……

某天，小 P 獲得了一張神秘的藏寶圖。

問題描述

西西艾弗島上種有 n 棵樹，這些樹的具體位置記錄在一張綠化圖上。
簡單地說，西西艾弗島綠化圖可以視作一個大小為 (L+1)×(L+1) 的 01 矩陣 A，
地圖左下角（坐標 (0,0)）和右上角（坐標 (L,L)）分別對應 A[0][0] 和 A[L][L]。
其中 A[i][j]=1 表示坐標 (i,j) 處種有一棵樹，A[i][j]=0 則表示坐標 (i,j) 處沒有樹。
換言之，矩陣 A 中有且僅有的 n 個 1 展示了西西艾弗島上 n 棵樹的具體位置。

傳說，大冒險家頓頓的寶藏就埋藏在某棵樹下。
並且，頓頓還從西西艾弗島的綠化圖上剪下了一小塊，制作成藏寶圖指示其位置。
具體來說，藏寶圖可以看作一個大小為 (S+1)×(S+1) 的 01 矩陣 B（S 遠小於 L），對應著 A 中的某一部分。
理論上，綠化圖 A 中存在著一處坐標 (x,y)（0≤x,y≤L−S）與藏寶圖 B 左下角 (0,0) 相對應，即滿足：
對 B 上任意一處坐標 (i,j)（0≤i,j≤S），都有 A[x+i][y+j]=B[i][j]。
當上述條件滿足時，我們就認為藏寶圖 B 對應著綠化圖 A 中左下角為 (x,y)、右上角為 (x+S,y+S) 的區域。

實際上，考慮到藏寶圖僅描繪了很小的一個范圍，滿足上述條件的坐標 (x,y) 很可能存在多個。
請結合西西艾弗島綠化圖中 n 棵樹的位置，以及小 P 手中的藏寶圖，判斷綠化圖中有多少處坐標滿足條件。

特別地，藏寶圖左下角位置一定是一棵樹，即 A[x][y]=B[0][0]=1，表示了寶藏埋藏的位置。

輸入格式

從標准輸入讀入數據。

輸入的第一行包含空格分隔的三個正整數 n、L 和 S，分別表示西西艾弗島上樹的棵數、綠化圖和藏寶圖的大小。

由於綠化圖尺寸過大，輸入數據中僅包含 n 棵樹的坐標而非完整的地圖；即接下來 n 行每行包含空格分隔的兩個整數 x 和 y，表示一棵樹的坐標，滿足 0≤x,y≤L 且同一坐標不會重復出現。

最後 (S+1) 行輸入小 P 手中完整的藏寶圖，其中第 i 行（0≤i≤S）包含空格分隔的 (S+1) 個 0 和 1，表示 B[S−i][0]⋯B[S−i][S]。
需要注意，最先輸入的是 B[S][0]⋯B[S][S] 一行，B[0][0]⋯B[0][S] 一行最後輸入。

輸出格式

輸出到標准輸出。

輸出一個整數，表示綠化圖中有多少處坐標可以與藏寶圖左下角對應，即可能埋藏著頓頓的寶藏。

樣例 1 輸入

5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0

樣例 1 輸出

3

樣例 1 解釋

綠化圖上 (0,0)、(1,1) 和 (2,2) 三處均可能埋有寶藏。

樣例 2 輸入

5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0

樣例 2 輸出

0

樣例 2 解釋

如果將藏寶圖左下角與綠化圖 (3,3) 處對應，則藏寶圖右上角會超出綠化圖邊界，對應不成功。

子任務

40% 的測試數據滿足：L≤50；

70% 的測試數據滿足：L≤2000；

全部的測試數據滿足：n≤1000、L≤109 且 S≤50。

提示

實際測試數據中不包括答案為 0 的用例。

真題來源：尋寶！大冒險！

 感興趣的同學可以進去進行練習提交

70分題解：內存超限

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)

運行結果：

ccf-csp練習專欄  

https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482