मान लीजिए h × w आयाम का एक ग्रिड है। ग्रिड को 2D सरणी 'initGrid' में दर्शाया गया है, जहाँ प्रत्येक सेल या तो '#' या '.' से दर्शाई गई है। '#' का अर्थ है ग्रिड में बाधा है और '.' का अर्थ है उस सेल से पथ है। अब, एक रोबोट को ग्रिड पर सेल 'c' पर रखा गया है जिसकी पंक्ति संख्या x और स्तंभ संख्या y है। रोबोट को दूसरी सेल 'd' तक जाना है जिसकी पंक्ति संख्या p और स्तंभ संख्या q है। सेल c और d के निर्देशांक हमें पूर्णांक युग्म के रूप में दिए गए हैं। अब, रोबोट एक सेल से दूसरी सेल पर निम्न तरीकों से जा सकता है:
- रोबोट केवल एक सेल से दूसरी सेल पर चल सकता है यदि वह सेल वर्तमान सेल से लंबवत या क्षैतिज रूप से आसन्न हो।
- रोबोट 5×5 क्षेत्र में किसी भी सेल पर कूद सकता है जिसका केंद्र वह सेल है जहाँ वह वर्तमान में स्थित है।
- रोबोट केवल तभी दूसरी सेल पर जा सकता है यदि गंतव्य सेल में बाधा न हो। रोबोट ग्रिड से बाहर भी नहीं जा सकता।
हमें गंतव्य तक पहुँचने के लिए आवश्यक कूद की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", "...#", "..#."}, तो आउटपुट 1 होगा। रोबोट को अपने गंतव्य तक पहुँचने के लिए केवल एक कूद की आवश्यकता होगी।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
N := 100
पूर्णांक युग्म s, t परिभाषित करें
आकार N का सरणी grid परिभाषित करें
आकार N×N का सरणी dst परिभाषित करें
एक संरचना node परिभाषित करें जिसमें पूर्णांक मान a, b, e हों
एक फंक्शन check() परिभाषित करें जो a, b लेता है:
लौटाएँ a >= 0 AND a < h AND b >= 0 AND b < w
एक फंक्शन bfs() परिभाषित करें जो a, b लेता है:
i := 0 से h-1 तक:
j := 0 से w-1 तक:
dst[i][j] := अनंत
dst[a][b] := 0
एक डेक doubleq परिभाषित करें
मान {a, b, dst[a][b]} वाला नोड doubleq के अंत में डालें
जब तक doubleq खाली न हो:
nd := doubleq का पहला तत्व
यदि nd का e मान > dst[nd.a][nd.b], तो जारी रखें
diffx := -2 से 2 तक:
diffy := -2 से 2 तक:
tm := |diffx| + |diffy|
nx := nd.a + diffx, ny := nd.b + diffy
यदि check(nx, ny) और grid[nx][ny] == '.', तो:
w := (यदि tm > 1 तो 1 अन्यथा 0)
यदि dst[nd.a][nd.b] + w < dst[nx][ny], तो:
dst[nx][ny] := dst[nd.a][nd.b] + w
यदि w == 0, तो:
मान {nx, ny, dst[nx][ny]} वाला नोड doubleq के शुरुआत में डालें
अन्यथा:
मान {nx, ny, dst[nx][ny]} वाला नोड doubleq के अंत में डालें
s := c
t := d
s के पहले मान को 1 घटाएँ
s के दूसरे मान को 1 घटाएँ
t के पहले मान को 1 घटाएँ
t के दूसरे मान को 1 घटाएँ
i := 0 से h-1 तक:
grid[i] := initGrid[i]
bfs(s का पहला मान, s का दूसरा मान)
प्रिंट करें (यदि dst[t का पहला मान][t का दूसरा मान] == अनंत तो -1 अन्यथा dst[t का पहला मान][t का दूसरा मान])
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; #define N 100 int h, w; pair<int, int> s, t; string grid[N]; int dst[N][N]; struct node { int a, b, e; }; bool check(int a, int b) { return a >= 0 && a < h && b >= 0 && b < w; } void bfs(int a, int b) { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) dst[i][j] = INF; } dst[a][b] = 0; deque<node> doubleq; doubleq.push_back({a, b, dst[a][b]}); while (!doubleq.empty()) { node nd = doubleq.front(); doubleq.pop_front(); if (nd.e > dst[nd.a][nd.b]) continue; for (int diffx = -2; diffx <= 2; diffx++) { for (int diffy = -2; diffy <= 2; diffy++) { int tm = abs(diffx) + abs(diffy); int nx = nd.a + diffx, ny = nd.b + diffy; if (check(nx, ny) && grid[nx][ny] == '.') { int w = (tm > 1) ? 1 : 0; if (dst[nd.a][nd.b] + w < dst[nx][ny]) { dst[nx][ny] = dst[nd.a][nd.b] + w; if (w == 0) doubleq.push_front({nx, ny, dst[nx][ny]}); else doubleq.push_back({nx, ny, dst[nx][ny]}); } } } } } } void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){ s = c; t = d; s.first--, s.second--, t.first--, t.second--; for(int i = 0; i < h; i++) grid[i] = initGrid[i]; bfs(s.first, s.second); cout << (dst[t.first][t.second] == INF ? -1 : dst[t.first][t.second]) << '\n'; } int main() { h = 4, w = 4; pair<int,int> c = {2, 1}, d = {4, 4}; string initGrid[] = {"#...", ".##.", "...#", "..#."}; solve(c, d, initGrid); return 0; }
इनपुट
4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}
आउटपुट
1