मान लीजिए हम एक सरलीकृत Pacman गेम खेल रहे हैं। अब हम बिंदु (0, 0) से शुरू करते हैं, और हमारा गंतव्य (target[0], target[1]) है। मैप पर कई भूत हैं, यहां i-th भूत (ghosts[i][0], ghosts[i][1]) से शुरू होता है। प्रत्येक मोड़ में, हम और सभी भूत एक साथ (हो सकता है) 4 मुख्य दिशाओं में से एक में चलते हैं - उत्तर, पूर्व, पश्चिम, या दक्षिण, अंतिम बिंदु से 1 यूनिट दूरी पर एक नए बिंदु पर जा रहे हैं। हम तभी बच सकते हैं जब हम किसी भी भूत के हम तक पहुंचने से पहले लक्ष्य तक पहुंच सकें (भूतों द्वारा लिए गए किसी भी दिए गए चाल के लिए)। यदि हम किसी भी वर्ग (लक्ष्य सहित) पर उसी समय पहुंचते हैं जब एक भूत, तो यह पलायन के रूप में नहीं गिना जाता है। तो हमें तब True लौटाना है जब पलायन करना संभव हो।
तो यदि इनपुट [[1,0], [0,3]] जैसा है, और लक्ष्य [0,1] है, तो परिणाम true होगा। ऐसा इसलिए है क्योंकि हम सीधे गंतव्य (0, 1) पर समय 1 पर पहुंच सकते हैं, जबकि (1, 0) या (0, 3) पर स्थित भूतों के पास हमें पकड़ने का कोई रास्ता नहीं है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- me := |target[1]| + |target[0]|
- x := 0
- i को 0 से भूत सरणी के आकार - 1 की रेंज में
- x := |ghosts[i,0] - target[0]| + |ghosts[i, 1] - target[1]|
- यदि x <= me, तो false लौटाएं
- true लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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