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

C++ में भूमि से यथासंभव दूर


मान लीजिए हमारे पास एक N x N ग्रिड है जिसमें केवल 0 और 1 जैसे मान हैं, जहां 0 पानी दर्शाता है और 1 भूमि दर्शाता है, हमें एक पानी का सेल ढूंढना है जिसकी निकटतम भूमि सेल से दूरी अधिकतम हो और दूरी लौटानी है। यहां हम मैनहट्टन दूरी का उपयोग करेंगे - दो सेल (x0, y0) और (x1, y1) के बीच की दूरी |x0 - x1| + |y0 - y1| है। यदि ग्रिड में कोई भूमि या पानी मौजूद नहीं है, तो -1 लौटाएं।

101
000
101

तब आउटपुट 2 होगा, क्योंकि सेल (1,1) दूरी 2 के साथ सभी भूमि से यथासंभव दूर है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • dir := [(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1), (0, -1)]
  • dir2 := [(1, 0), (-1, 0), (0, 1), (0, -1)]
  • एक मैप m परिभाषित करें। एक क्यू q परिभाषित करें। n := पंक्ति गणना और c := कॉलम गणना
  • i को 0 से n - 1 तक लूप करें
    • j को 0 से n - 1 तक लूप करें
      • यदि grid[i, j] = 1, तो जोड़ी (i, j) को q में डालें और m[(i, j)] := (j, i) रखें
  • ret := -1
  • जब तक q खाली नहीं है
    • sz := q का आकार
    • जब तक sz 0 नहीं है
      • temp := q का पहला तत्व, q से पहला तत्व हटाएं
      • k को 0 से 3 तक लूप करें
        • nx := temp का पहला मान + dir2[k, 0]
        • ny := temp का दूसरा मान + dir2[k, 1]
        • यदि nx और ny ग्रिड की सीमा में नहीं हैं, या grid[nx, ny] = 1, तो अगले पुनरावृत्ति पर जाएं।
        • m[(nx, ny)] := m[temp]
        • ret := (nx, ny) और m(temp) की दूरी और ret का अधिकतम
        • (nx,ny) को q में डालें
        • grid[nx, ny] := 1 सेट करें
      • sz को 1 से घटाएं
  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int dir[8][2] = {    {1, 0}, {-1, 0}, {1, -1}, {1, 1},    {-1, 1}, {-1, -1}, {0, 1}, {0, -1} }; int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution {    public:    int calcDist(int x1, int y1, int x2, int y2){       return abs(x1 - x2) + abs(y1 - y2);    }    int maxDistance(vector<vector<int>>& grid) {       map < pair <int, int>, pair <int, int> > m;       queue < pair <int, int> > q;       int n = grid.size();       int c = n? grid[0].size() : 0;       for(int i = 0; i < n; i++){          for(int j = 0; j < c; j++){             if(grid[i][j] == 1){                q.push({i, j});                m[{i, j}] = {i, j};             }          }       }       int ret = -1;       while(!q.empty()){          int sz = q.size();          while(sz--){             pair <int, int> temp = q.front();             q.pop();             for(int k = 0; k < 4; k++){                int nx = temp.first + dir2[k][0];                int ny = temp.second + dir2[k][1];                if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;                m[{nx, ny}] = m[temp];                ret = max(calcDist(nx, ny, m[temp].first,                m[temp].second), ret);                q.push({nx, ny});                grid[nx][ny] = 1;             }          }       }       return ret;    } }; main(){    vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};    Solution ob;    cout << (ob.maxDistance(v1)); }

इनपुट

[[1,0,1],[0,0,0],[1,0,1]]

आउटपुट

2

  1. - C++ में static_cast

    static_cast का उपयोग सामान्य/साधारण प्रकार रूपांतरण के लिए किया जाता है। यह निहित प्रकार जबरदस्ती (implicit type coercion) के लिए भी जिम्मेदार कास्ट है और इसे स्पष्ट रूप से भी बुलाया जा सकता है। आपको इसका उपयोग फ्लोट को इंट में, चार को इंट में आदि जैसे मामलों में करना चाहिए। यह संबंधित प्रकार के क्

  1. - C++ फंक्शन से एकाधिक मान वापस करना

    C या C++ में, हम सीधे एक फंक्शन से एकाधिक मान वापस नहीं कर सकते। इस सेक्शन में हम देखेंगे कि एक फंक्शन से एक से अधिक मान वापस करने के लिए कुछ ट्रिक का उपयोग कैसे करें। हम कॉल बाय एड्रेस या कॉल बाय रेफरेंस मेथड का उपयोग करके एक फंक्शन से एक से अधिक मान वापस कर सकते हैं। इन्वोकर फंक्शन में हम परिणाम

  1. - C++ में फंक्शन से सरणी कैसे लौटाएं?

    C++ पूरी सरणी नहीं लौटाता लेकिन यह सरणी का पॉइंटर लौटा सकता है। फंक्शन के बाहर, लोकल वेरिएबल का पता नहीं लौटाया जा सकता। लोकल वेरिएबल को स्टैटिक बनाकर, यह लोकल वेरिएबल का पता लौटा सकता है। पॉइंटर लौटाने का सिंटैक्स निम्नलिखित है। int * function_name() { body } यहां, function_name − उपयोगकर्ता