মান লিজিয়ে, x × y মাত্রার একটি গ্রিড দেওয়া আছে যাতে দুটি ধরনের কক্ষ রয়েছে: ব্লক করা এবং আনব্লক করা। ব্লক করা কক্ষ মানে অ্যাক্সেস করা যাবে না এবং আনব্লক করা মানে অ্যাক্সেস করা যাবে। গ্রিডটি ২D অ্যারে আকারে দেওয়া আছে যেখানে ব্লক করা কক্ষ '#' এবং আনব্লক করা কক্ষ '.' দিয়ে দেখানো হয়েছে। এখন আমাদের (0, 0) কক্ষ থেকে (x, y) কক্ষে যেতে হবে। আমরা শুধু দুটি মোভ করতে পারি: একটি কক্ষের ডানে যেতে বা নিচে যেতে। লক্ষ্য করুন যে, আমরা শুধু আনব্লক কক্ষেই যেতে পারি, এবং (0, 0) ও (x, y) উভয়ই আনব্লক। যদি (0, 0) থেকে (x, y) যাওয়া সম্ভব না হয়, তবে আমরা একটি ব্লক করা কক্ষকে আনব্লক করতে পারি। আমাদের লক্ষ্য হলো গন্তব্যে পৌঁছাতে ন্যূনতম কতটি পরিবর্তন অপারেশন করতে হবে তা বের করা।
যেমন, ইনপুট হলে x = 4, y = 4, grid = {"..#.", "#.#.", "#.##", "###."}, তবে আউটপুট হবে 1।
শুধু একটি পরিবর্তন অপারেশন করতে হবে। যদি (2, 2) কক্ষকে ব্লক থেকে আনব্লক করি, তবে (0, 0) থেকে (3, 3) যাওয়া সম্ভব হবে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
mat ২D অ্যারে সংজ্ঞায়িত করুন if grid[0, 0] == '#', তবে: mat[0, 0] := 1 অন্যথায়: mat[0, 0] := 0 i := 0 থেকে x-1 পর্যন্ত: j := 0 থেকে y-1 পর্যন্ত: if i+1 < x, তবে: mat[i+1, j] = min(mat[i+1, j], mat[i, j] + (1 যদি grid[i+1, j] == '#' এবং grid[i, j] == '.')) if j+1 < y, তবে: mat[i, j+1] = min(mat[i, j+1], mat[i, j] + (1 যদি grid[i, j+1] == '#' এবং grid[i, j] == '.')) return mat[x-1, y-1]
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int solve(int x, int y, vector<string> grid){ vector<vector<int>> mat(x, vector<int>(y, 100)); if(grid[0][0] == '#') mat[0][0] = 1; else mat[0][0] = 0; for(int i = 0; i < x; i++){ for(int j = 0; j < y; j++){ if(i + 1 < x){ mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.')); } if(j + 1 < y){ mat[i][j + 1] = min(mat[i][j + 1],mat[i][j]+(grid[i][j + 1] == '#' && grid[i][j] == '.')); } } } return mat[x - 1][y - 1]; } int main() { int x = 4, y = 4; vector<string> grid = {"..#.", "#.#.", "#.##", "###."}; cout<< solve(x, y, grid); return 0; } ইনপুট
4, 4, {"..#.", "#.#.", "#.##", "###."} আউটপুট
1
