#41996: 關於如何找曼哈論距離
s10900156@nhsh.tp.edu.tw
(ShanC)
學校
:
臺北市立內湖高級中學
編號 : 138785
來源 : [118.167.202.23]
最後登入時間 ：
2024-11-29 20:43:48
應該有些人卡在不知道怎麼在網格上找曼哈頓距離
因這題的曼哈論距離範圍是介於 0~9
而且網格大小也才 50 * 50
因此我是直接用窮舉的作法
對於每個 (x, y) 窮舉他的 x 軸範圍 (-9~9) 與 y 軸範圍 (-9~9)
時間複雜度 O(n * m * 19 * 19) = O(n * m)
bool check(int x, int y) {
for (int i = -9; i <= 9; i++) {
for (int j = -9; j <= 9; j++) {
int dx = x + i, dy = y + j;
// 判斷的東西在這邊
}
}
// 回傳答案
}