目錄
- 問題描述
- 思路分析及代碼實作
問題描述
小藍在一張無限大的特殊畫布上作畫， 這張畫布可以看成一個方格圖，每個格子可以用一個二維的整數坐標表示，
小藍在畫布上首先點了一下幾個點：(0, 0), (2020, 11), (11, 14), (2000, 2000)，
只有這幾個格子上有黑色，其它位置都是白色的， 每過一分鐘，黑色就會擴散一點，具體的，如果一個格子里面是黑色，它
就會擴散到上、下、左、右四個相鄰的格子中，使得這四個格子也變成黑色 （如果原來就是黑色，則還是黑色）， 請問，經過 2020分鐘后，畫布上有多少個格子是黑色的，
思路分析及代碼實作
看到這道題之后，首先想到的是DFS，無奈水平有限，實在想不明白怎么下手，于是變換了思路，找任意點來判斷能不能被染黑，如果這個點能夠在2020步內走到，那一定能被染黑，那么現在就變成了已知兩點的坐標，求兩點的距離，然后這個距離就是曼哈頓距離，其運算式為d(i,j) = |x1-x2| + |y1-y2|,然后就是找這個任意點的范圍，總不能讓他隨意出現吧，，，
通過分析可知x的下限就是已知的四個點的最小值-2020，x的上限就是x的最大值+2020，同理y也是一樣
代碼：
xy = [[0, 0], [2020, 11], [11, 14], [2000, 2000]]
ans = 0
for i in range(-2020, 4041):
for j in range(-2020, 4021):
for k in range(4):
if abs(i-xy[k][0]) + abs(j-xy[k][1]) <= 2020:
ans += 1
break
print(ans)
答案：20312088
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256448.html
標籤：python