मान लीजिए हमारे पास H पंक्तियों और W कॉलम वाला एक मैट्रिक्स है। सेल या तो '.' या '#' रखते हैं। डॉट '.' पास करने योग्य स्थान को दर्शाता है, और '#' ब्लॉक को दर्शाता है। अमल अपने घर से बाजार जाएगा। उसका घर शीर्ष-बाएं कोने के सेल में है, और बाजार नीचे-दाएं कोने में है। अमल पास करने योग्य सेल में एक सेल ऊपर, नीचे, बाएं, या दाएं जा सकता है। वह शहर नहीं छोड़ सकता। वह ब्लॉक सेल में भी प्रवेश नहीं कर सकता। हालांकि, उसकी शारीरिक ताकत उसे अपनी पसंद के 2x2 सेल के वर्ग क्षेत्र में सभी ब्लॉक को एक पंच से नष्ट करने की अनुमति देती है, जिससे ये सेल पास करने योग्य हो जाते हैं। हमें अमल के लिए बाजार तक पहुंचने के लिए आवश्यक न्यूनतम पंच की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है:
| . | . | # | . | . |
| # | . | # | . | # |
| # | # | . | # | # |
| # | . | # | . | # |
| . | . | # | . | . |
तो आउटपुट 1 होगा, क्योंकि हम ग्रिड को ऐसा बना सकते हैं:
| . | . | # | . | . |
| # | . | . | . | # |
| # | # | . | . | # |
| # | . | # | . | # |
| . | . | # | . | . |
चिह्नित बॉक्स को नष्ट करके
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := मैट्रिक्स की पंक्ति संख्या m := मैट्रिक्स की कॉलम संख्या क्रम (n + 1) x (m + 1) का एक 2D ऐरे dist परिभाषित करें एक डीक्यू dq परिभाषित करें (0, 0) को dq की शुरुआत में डालें dist[0, 0] := 0 जब तक (dq खाली नहीं है), करें: v := dq का पहला तत्व dq से सामने का तत्व हटाएं i := 0 से 3 तक, करें: x := dx[i] + v[0] y := dy[i] + v[1] यदि x >= 0 और x < n और y >= 0 और y < m, तो: यदि matrix[x, y], '.' के बराबर है, तो: यदि dist[x, y] > dist[v[0], v[1]], तो: dist[x, y] := dist[v[0], v[1]] युग्म { x, y } को dq की शुरुआत में डालें अन्यथा p := x - 1 से x + 1 तक, करें: q := y - 1 से y + 1 तक, करें: यदि p >= 0 और p < n और q >= 0 और q < m, तो: यदि dist[p, q] > dist[v[0], v[1]] + 1, तो: dist[p, q] := dist[v[0], v[1]] + 1 युग्म { p, q } को dq के अंत में डालें dist[n - 1, m - 1] वापस करें उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { -1, 1, 0, 0 }; int solve(vector<vector<char>> matrix){ int n = matrix.size(); int m = matrix[0].size(); vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9)); deque<array<int, 2>> dq; dq.push_front({ 0, 0 }); dist[0][0] = 0; while (!dq.empty()){ auto v = dq.front(); dq.pop_front(); for (int i = 0; i < 4; i++){ int x = dx[i] + v[0], y = dy[i] + v[1]; if (x >= 0 && x < n && y >= 0 && y < m){ if (matrix[x][y] == '.'){ if (dist[x][y] > dist[v[0]][v[1]]){ dist[x][y] = dist[v[0]][v[1]]; dq.push_front({ x, y }); } } else{ for (int p = x - 1; p <= x + 1; p++){ for (int q = y - 1; q <= y + 1; q++){ if (p >= 0 && p < n && q >= 0 && q < m){ if (dist[p][q] > dist[v[0]][v[1]] + 1){ dist[p][q] = dist[v[0]][v[1]] + 1; dq.push_back({ p, q }); } } } } } } } } return dist[n - 1][m - 1]; } int main(){ vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } }; cout << solve(matrix) << endl; } इनपुट
{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } } आउटपुट
1