C++ এ পাথ যোগফল IV

ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি তালিকা রয়েছে যা 5-এর চেয়ে ছোট গভীরতা সহ একটি বাইনারি ট্রিকে প্রতিনিধিত্ব করছে৷ যদি একটি গাছের গভীরতা 5-এর কম হয়, তাহলে এই গাছটিকে তিন-সংখ্যার পূর্ণসংখ্যাগুলির একটি তালিকা দ্বারা উপস্থাপন করা যেতে পারে৷ এই তালিকার প্রতিটি পূর্ণসংখ্যার জন্য -

শত সংখ্যা এই নোডের গভীরতা D প্রতিনিধিত্ব করছে, 1 <=D <=4।
দশ সংখ্যাটি এই নোডের অবস্থান P কে প্রতিনিধিত্ব করছে যে স্তরে এটি 1 থেকে 8 এর মধ্যে রয়েছে। অবস্থানটি সম্পূর্ণ বাইনারি গাছের মতোই।
এই নোডের V মান, 0 <=V <=9।

আমাদের মূল থেকে পাতার দিকে সমস্ত পথের যোগফল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি [113, 215, 221] এর মত হয়, তাহলে আউটপুট হবে 12, তালিকাটি যে ট্রিটি উপস্থাপন করে তা হল

C++ এ পাথ যোগফল IV

পথের যোগফল হল (3 + 5) + (3 + 1) =12।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র গ্রাফ সংজ্ঞায়িত করুন
একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, স্তর, pos, যোগফল 0 দিয়ে শুরু করবে,
isLeaf :=সত্য
আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার [লেভেল + 1], আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
- এক জোড়া তাপমাত্রা সংজ্ঞায়িত করুন :=গ্রাফ [স্তর + 1, i]
- যদি temp.first / 2 pos এর মত হয়, তাহলে −
  - isLeaf :=মিথ্যা
  - dfs(temp.second, level + 1, temp.first, sum + node)
যদি isLeaf অ-শূন্য হয়, তাহলে −
- ret :=ret + (সমষ্টি + নোড)
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন,
ret :=0
আরম্ভ করার জন্য i :=0, যখন i <সংখ্যার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
- x :=সংখ্যা[i]
- val :=x mod 10
- x :=x / 10
- pos :=x mod 10
- x :=x / 10
- স্তর :=x
- সন্নিবেশ করান { (1 বাম দিকে স্থানান্তর করুন (স্তর - 1) বার), val } গ্রাফের শেষে [স্তর]
dfs(গ্রাফ[1, 0].সেকেন্ড, 1, গ্রাফ[1, 0].প্রথম)
রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ret;
   map <int, vector < pair <int, int> > > graph;
   void dfs(int node, int level, int pos, int sum = 0){
      bool isLeaf = true;
      for (int i = 0; i < graph[level + 1].size(); i++) {
         pair<int, int> temp = graph[level + 1][i];
         if (temp.first / 2 == pos) {
            isLeaf = false;
            dfs(temp.second, level + 1, temp.first, sum + node);
         }
      }
      if (isLeaf) {
         ret += (sum + node);
      }
   }
   int pathSum(vector<int>& nums) {
      ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         int val = x % 10;
         x /= 10;
         int pos = x % 10;
         x /= 10;
         int level = x;
         graph[level].push_back({ (1 << (level - 1)) + pos - 1, val });
      }
      dfs(graph[1][0].second, 1, graph[1][0].first);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {113,215,221};
   cout<<(ob.pathSum(v));
}

ইনপুট

{113,215,221}