Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में टारगेट कलर तक सबसे छोटी दूरी


मान लीजिए हमारे पास एक कलर ऐरे है जिसमें तीन कलर्स हैं: 1, 2 और 3। हमें कुछ क्वेरीज़ दी गई हैं। प्रत्येक क्वेरी में दो इंटीजर्स i और c होते हैं, हमें दिए गए इंडेक्स i और टारगेट कलर c के बीच सबसे छोटी दूरी ढूंढनी है। अगर कोई समाधान नहीं है, तो -1 लौटाएं। उदाहरण के लिए, अगर कलर्स ऐरे है [1,1,2,1,3,2,2,3,3], और क्वेरीज़ ऐरे है [[1,3], [2,2], [6,1]], तो आउटपुट होगा [3,0,3]। ऐसा इसलिए क्योंकि इंडेक्स 1 से निकटतम 3 इंडेक्स 4 पर है (3 स्टेप दूर)। फिर इंडेक्स 2 से निकटतम 2 इंडेक्स 2 पर ही है (0 स्टेप दूर)। और इंडेक्स 6 से निकटतम 1 इंडेक्स 3 पर है (3 स्टेप दूर)।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

  • 4 पंक्तियों वाला एक मैट्रिक्स idx बनाएं, n := कलर ऐरे में एलिमेंट्स की संख्या

  • i को 0 से n-1 तक लूप करें:

    • i को idx[colors[i]] में इंसर्ट करें

    • x := queries[i][0] और c := queries[i][1]

    • अगर idx[c] का साइज 0 है, तो ret में -1 इंसर्ट करें, और अगले इटरेशन पर जाएं

    • it := पहला एलिमेंट जो x से कम नहीं है - idx[c] का पहला एलिमेंट

    • op1 := इनफिनिटी, op2 := इनफिनिटी

    • अगर it = idx[c] का साइज, तो it को 1 घटाएं, op1 := |x - idx[c][it]|

    • अन्यथा जब it = 0, तो op1 := |x - idx[c][it]|

    • अन्यथा op1 := |x - idx[c][it]|, it को 1 घटाएं और op2 := |x - idx[c][it]|

    • ret में op1 और op2 का मिनिमम इंसर्ट करें

  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        vector < vector <int> > idx(4);
        int n = colors.size();
        for(int i = 0; i < n; i++){
            idx[colors[i]].push_back(i);
        }
        vector <int> ret;
        for(int i = 0; i < queries.size(); i++){
            int x = queries[i][0];
            int c = queries[i][1];
            if(idx[c].size() == 0){
                ret.push_back(-1);
                continue;
            }
            int it = lower_bound(idx[c].begin(), idx[c].end(), x) - idx[c].begin();
            int op1 = INT_MAX;
            int op2 = INT_MAX;
            if(it == idx[c].size()){
                it--;
                op1 = abs(x - idx[c][it]);
            }
            else if(it == 0){
                op1 = abs(x - idx[c][it]);
            }
            else{
                op1 = abs(x - idx[c][it]);
                it--;
                op2 = abs(x - idx[c][it]);
            }
            ret.push_back(min(op1, op2));
        }
        return ret;
    }
};

int main(){
    vector<int> v = {1,1,2,1,3,2,2,3,3};
    vector<vector<int>> v1 = {{1,3},{2,2},{6,1}};
    Solution ob;
    print_vector(ob.shortestDistanceColor(v, v1));
}

इनपुट

[1,1,2,1,3,2,2,3,3] [[1,3],[2,2],[6,1]]

आउटपुट

[3,0,3]

  1. OpenCV में C++ का उपयोग करके रंग को ट्रैक करें OpenCV में C++ का उपयोग करके रंग को ट्रैक करें

    रंग ट्रैकिंग रंग पहचान के समान है। ट्रैकिंग उद्देश्य के लिए, हमने पता लगाए गए ऑब्जेक्ट के क्षेत्र की गणना करने के लिए कुछ अतिरिक्त लाइनें जोड़ीं और फिर उस क्षेत्र की वर्तमान स्थिति को ट्रैक किया और अंत में ऑब्जेक्ट के गति पथ को दिखाने के लिए OpenCV के line() फंक्शन का उपयोग किया।OpenCV में C++ का उप

  1. मैनहट्टन दूरी के बराबर दूरी वाले पथों की गणना - C++ मैनहट्टन दूरी के बराबर दूरी वाले पथों की गणना - C++

    समस्या विवरण हमें दो बिंदु (x1, y1) और (x2, y2) दिए गए हैं। लक्ष्य उन सभी पथों की गणना करना है जिनकी दूरी इन बिंदुओं के बीच मैनहट्टन दूरी के बराबर हो। मैनहट्टन दूरी MD = |x1 - x2| + |y1 - y2| मान लें A = |x1 - x2|, B = |y1 - y2|। मैनहट्टन दूरी वाले सभी पथों में A क्षैतिज और B लंबवत किनारे होंगे। सं

  1. C++ में दो अलग-अलग गुड नोड्स की किसी भी जोड़ी के बीच सबसे छोटी दूरी खोजें C++ में दो अलग-अलग गुड नोड्स की किसी भी जोड़ी के बीच सबसे छोटी दूरी खोजें

    मान लीजिए हमारे पास N अलग-अलग नोड्स और M एजेज के साथ एक दिया गया वेटेड अनडायरेक्टेड ग्राफ है, कुछ नोड्स गुड नोड्स हैं। हमें किन्हीं दो अलग-अलग गुड नोड्स की जोड़ी के बीच सबसे छोटी दूरी खोजनी है। दिए गए आरेख में पीले नोड्स को गुड नोड्स माना जाता है। उदाहरण के लिए, यदि इनपुट इस तरह का है: तो आउटपुट 11