Giả sử chúng ta đang chơi một trò chơi Pacman đơn giản hóa. Bây giờ chúng ta bắt đầu tại điểm (0, 0) và đích của chúng ta là (target [0], target [1]). Có một số bóng ma trên bản đồ, Ở đây bóng ma thứ i bắt đầu tại (bóng ma [i] [0], bóng ma [i] [1]). Trong mỗi lượt, chúng ta và tất cả các hồn ma đồng thời (có thể) di chuyển theo một trong 4 hướng chính - bắc, đông, tây hoặc nam, đi từ điểm cuối cùng đến điểm mới cách đó 1 đơn vị khoảng cách. Chúng ta có thể trốn thoát nếu và chỉ khi chúng ta có thể tiếp cận mục tiêu trước khi bất kỳ con ma nào tiếp cận chúng ta (đối với bất kỳ động thái nhất định nào mà bóng ma có thể thực hiện.) Nếu chúng ta tiếp cận bất kỳ ô vuông nào (kể cả mục tiêu) cùng lúc với một con ma, thì không tính như một cuộc chạy trốn. Vì vậy, chúng tôi phải trả về True khi có thể thoát.
Vì vậy, nếu đầu vào là [[1,0], [0,3]] và mục tiêu là [0,1], thì kết quả sẽ là true. Điều này là do chúng ta có thể trực tiếp đến đích (0, 1) tại thời điểm 1, trong khi những con ma ở (1, 0) hoặc (0, 3) không có cách nào bắt được chúng ta.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tôi:=| target [1] | + | target [0] |
- x:=0
- cho tôi trong phạm vi từ 0 đến kích thước của mảng ma - 1
- x:=| ma [i, 0] - target [0] | + | ma [i, 1] - target [1] |
- nếu x <=me, thì trả về false
- trả về true
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[[1,0],[0,3]] [0,1]
Đầu ra
1