สมมติว่าเรากำลังเล่นเกม Pacman แบบง่าย ตอนนี้เราเริ่มต้นที่จุด (0, 0) และปลายทางของเราคือ (เป้าหมาย[0] เป้าหมาย[1]) มีผีอยู่หลายตัวบนแผนที่ ที่นี่ผีตัวที่ i เริ่มต้นที่ (ผี[i][0] ผี[i][1]) ในแต่ละเทิร์น เราและผีทั้งหมดพร้อมกัน (อาจ) จะเคลื่อนที่ไปในทิศทางใดทิศทางหนึ่งจาก 4 ทิศทาง ได้แก่ เหนือ ตะวันออก ตะวันตก หรือใต้ โดยเริ่มจากจุดสุดท้ายไปยังจุดใหม่ที่ห่างออกไป 1 หน่วย เราสามารถหลบหนีได้ก็ต่อเมื่อเราไปถึงเป้าหมายก่อนที่ผีจะมาหาเรา (สำหรับการเคลื่อนไหวใด ๆ ผีอาจใช้) หากเราไปถึงสี่เหลี่ยมจัตุรัสใด ๆ (รวมถึงเป้าหมาย) ในเวลาเดียวกันเป็นผีจะไม่ นับเป็นการหลบหนี ก็เลยต้องคืน True เมื่อหนีออกมาได้
ดังนั้นหากอินพุตเป็นเหมือน [[1,0], [0,3]] และเป้าหมายคือ [0,1] ผลลัพธ์จะเป็นจริง เนื่องจากเราสามารถไปถึงจุดหมายได้โดยตรง (0, 1) ที่เวลา 1 ในขณะที่ผีที่อยู่บริเวณ (1, 0) หรือ (0, 3) ไม่มีทางจับเราได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ฉัน :=|target[1]| + |target[0]|
- x :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของ ghost array – 1
- x :=|ghosts[i,0] – target[0]| + |ghosts[i, 1] – เป้าหมาย[1]|
- ถ้า x <=me ให้คืนค่าเท็จ
- คืนค่าจริง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
int me = abs(target[1]) + abs(target[0]);
int x = 0;
for(int i = 0; i < ghosts.size(); i++){
x = abs(ghosts[i][0] - target[0]) + abs(ghosts[i][1] - target[1]);
if(x <= me) return false;
}
return true;
}
};
main(){
vector<vector<int>> v1 = {{1,0}, {0,3}};
vector<int> v2 = {0,1};
Solution ob;
cout << (ob.escapeGhosts(v1, v2));
} อินพุต
[[1,0],[0,3]] [0,1]
ผลลัพธ์
1
