ধরুন, আমাদেরকে x * y মাত্রার একটি গ্রিড দেওয়া হয়েছে যেটিতে ব্লক করা এবং আনব্লক করা দুই ধরনের সেল রয়েছে। অবরুদ্ধ কক্ষের অর্থ হল কোষগুলি অ্যাক্সেসযোগ্য নয় এবং অবরোধ মুক্ত করার অর্থ হল কোষগুলি অ্যাক্সেসযোগ্য৷ আমরা একটি 2D অ্যারেতে গ্রিডকে উপস্থাপন করি যেখানে ব্লক করা সেলগুলি '#' হিসাবে দেওয়া হয় এবং আনব্লক করা সেলগুলি '.' হিসাবে দেওয়া হয়। এখন, আমাদের সেল (0, 0) থেকে সেল (x, y) এ পৌঁছাতে হবে। আমরা শুধুমাত্র দুটি চাল সঞ্চালন করতে পারি, আমরা হয় একটি ঘরের ডানদিকে যেতে পারি বা একটি ঘর থেকে নিচে যেতে পারি। আমাদের মনে রাখতে হবে যে, আমরা শুধুমাত্র আনব্লক করা কক্ষে যেতে পারি এবং (0, 0) এবং (x, y) উভয়ই আনব্লক করা সেল। যদি আমরা (0, 0) থেকে (x, y) পৌঁছাতে না পারি, তাহলে আমরা একটি অবরুদ্ধ ঘরকে একটি আনব্লকড সেল করতে পারি। উৎস থেকে আমাদের গন্তব্যে পৌঁছানোর জন্য আমাদের সর্বনিম্ন পরিবর্তিত ক্রিয়াকলাপগুলি খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুট হয় x =4, y =4, গ্রিড ={"..#.", "#.#.", "#.##", "###।"}, তাহলে আউটপুট 1 হবে।
শুধুমাত্র একটি পরিবর্তন অপারেশন করতে হবে. যদি আমরা সেল (2, 2) কে অবরুদ্ধ থেকে আনব্লক করাতে পরিবর্তন করি, তাহলে আমরা (0, 0) থেকে (3, 3) পৌঁছাতে পারি।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one 2D array mat
if grid[0, 0] is same as '#', then:
mat[0, 0] := 1
Otherwise
mat[0, 0] := 0
for initialize i := 0, when i < x, update (increase i by 1), do:
for initialize j := 0, when j < y, update (increase j by 1), do:
if i + 1 < x, then:
mat[i + 1, j] = minimum of (mat[i + 1, j], mat[i, j] + (1 if grid[i + 1, j] is same as '#' AND grid[i, j] is same as '.'))
if j + 1 < y, then:
mat[i, j + 1] = minimum of (mat[i, j + 1], mat[i, j]+(1 if grid[i, j + 1] is same as '#' AND grid[i, j] is same as '.'))
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
