मान लीजिए x × y आयाम का एक ग्रिड दिया गया है जिसमें दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। ब्लॉक सेल पहुँच योग्य नहीं हैं और अनब्लॉक पहुँच योग्य हैं। ग्रिड को 2D सरणी में दर्शाया गया है जहाँ ब्लॉक सेल '#' और अनब्लॉक सेल '.' से दर्शाए गए हैं। अब हमें सेल (0, 0) से सेल (x, y) तक पहुँचना है। हम केवल दो चालें कर सकते हैं: किसी सेल के दाएँ जाना या किसी सेल से नीचे जाना। ध्यान रखें कि हम केवल अनब्लॉक सेल्स पर जा सकते हैं, और (0, 0) और (x, y) दोनों अनब्लॉक हैं। यदि हम (0, 0) से (x, y) नहीं पहुँच सकते, तो हम ब्लॉक सेल को अनब्लॉक बना सकते हैं। हमें गंतव्य तक पहुँचने के लिए आवश्यक न्यूनतम परिवर्तन ऑपरेशन्स की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है x = 4, y = 4, grid = {"..#.", "#.#.", "#.##", "###."}, तो आउटपुट 1 होगा।
केवल एक परिवर्तन ऑपरेशन करना होगा। यदि हम सेल (2, 2) को ब्लॉक से अनब्लॉक में बदल दें, तो हम (0, 0) से (3, 3) पहुँच सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक 2D सरणी mat परिभाषित करें
यदि grid[0][0] == '#', तो mat[0][0] := 1 अन्यथा mat[0][0] := 0
i := 0 से x-1 तक:
j := 0 से y-1 तक:
यदि i+1 < x, तो:
mat[i+1][j] = min(mat[i+1][j], mat[i][j] + (1 यदि grid[i+1][j]=='#' और grid[i][j]=='.'))
यदि j+1 < y, तो:
mat[i][j+1] = min(mat[i][j+1], mat[i][j] + (1 यदि grid[i][j+1]=='#' और grid[i][j]=='.'))
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