मान लीजिए, हमें x * y आयामों का एक ग्रिड दिया गया है जिसमें दो प्रकार के सेल हैं, ब्लॉक और अनब्लॉक। अवरुद्ध कोशिकाओं का अर्थ है कि कोशिकाएँ पहुँच योग्य नहीं हैं और अवरोधरहित का अर्थ है कि कोशिकाएँ पहुँच योग्य हैं। हम 2डी सरणी में ग्रिड का प्रतिनिधित्व करते हैं जहां अवरुद्ध कोशिकाओं को '#' के रूप में दिया जाता है और अनब्लॉक कोशिकाओं को '।' के रूप में दिया जाता है। अब, हमें सेल (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