মান लीजिए, h × w মাত্রার একটি গ্রিড দেওয়া আছে। গ্রিডের প্রতিটি কক্ষে একটি নির্দিষ্ট মান অর্পিত। আমাদের লক্ষ্য হলো সম মানযুক্ত কক্ষের সংখ্যা সর্বাধিক করা। এর জন্য, আমরা একটি কক্ষ নির্বাচন করতে পারি যা পূর্বে নির্বাচিত হয়নি, এবং তারপর ওই কক্ষের মান ১ কমিয়ে, বর্তমান কক্ষের খাড়া বা দাঁড়ি থেকে সংলগ্ন অন্য একটি কক্ষের মান ১ বাড়াতে পারি। আমরা অপারেশনের সংখ্যা এবং কমানো ও বাড়ানো কক্ষের অবস্থান প্রিন্ট করব। আউটপুটের ফরম্যাট নিচের মতো হবে:
অপারেশনের সংখ্যা
১ম (কমানো কক্ষের অবস্থান) - (বাড়ানো কক্ষের অবস্থান)
....
n-তম (কমানো কক্ষের অবস্থান) - (বাড়ানো কক্ষের অবস্থান)
যেমন, ইনপুট হলে h = 3, w = 3, grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}, তবে আউটপুট হবে:
4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
নতুন একটি অ্যারে result সংজ্ঞায়িত করুন যা টাপল ধারণ করবে i := 0 দিয়ে আরম্ভ করুন, i < h হলে, (i ১ বাড়িয়ে) করুন: tp := 0 j := 0 দিয়ে আরম্ভ করুন, j < w হলে, (j ১ বাড়িয়ে) করুন: if tp > 0, তবে: টাপল (i, j-1, i, j) result-র শেষে যোগ করুন grid[i, j] := grid[i, j] + tp if grid[i, j] mod 2 == 1 এবং j < w-1, তবে: grid[i, j] := grid[i, j] - 1 tp := 1 অন্যথায় tp := 0 tp := 0 i := 0 দিয়ে আরম্ভ করুন, i < h হলে, (i ১ বাড়িয়ে) করুন: if tp > 0, তবে: টাপল (i-1, w-1, i, w-1) result-র শেষে যোগ করুন grid[i, w-1] := grid[i, w-1] + tp if grid[i, w-1] mod 2 == 1, তবে: grid[i, w-1] := grid[i, w-1] - 1 tp := 1 অন্যথায় tp := 0 result-র আকার প্রিন্ট করুন i := 0 দিয়ে আরম্ভ করুন, i < result-র আকার হলে, (i ১ বাড়িয়ে) করুন: প্রিন্ট করুন: '(' + result[i]-র ১ম মান + ',' + result[i]-র ২য় মান + ')- (' + result[i]-র ৩য় মান + ',' + result[i]-র ৪র্থ মান + ')' উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; void solve(int h, int w, vector<vector<int>>grid){ vector<tuple<int,int,int,int>> result; for(int i = 0; i < h; i++){ int tp = 0; for(int j = 0; j < w; j++){ if(tp > 0){ result.push_back(make_tuple(i, j-1, i, j)); grid[i][j] += tp; } if(grid[i][j]%2 == 1 && j < w-1){ grid[i][j] -= 1; tp = 1; } else tp = 0; } } int tp = 0; for(int i = 0; i < h; i++){ if(tp > 0){ result.push_back(make_tuple(i-1, w-1, i, w-1)); grid[i][w-1] += tp; } if(grid[i][w-1]%2 == 1){ grid[i][w-1] -= 1; tp = 1; } else tp = 0; } cout << (int)result.size() << endl; for(int i = 0; i < (int)result.size(); i++){ cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i]) << ")" << " - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")"; cout << '\n'; } } int main() { int h = 3, w = 3 ; vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}; solve(h, w, grid); return 0; } ইনপুট
3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}} আউটপুট
4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)
