C++ প্রোগ্রাম: গ্রিডের সব কক্ষ কালো করার জন্য প্রয়োজনীয় ইটারেশন গণনা

মান লিজিয়ে, একটি গ্রিড দেওয়া আছে যাতে দুটি ধরনের কক্ষ রয়েছে: কালো কক্ষ এবং সাদা কক্ষ। কালো কক্ষ '#' দিয়ে এবং সাদা কক্ষ '.' দিয়ে প্রতীকীভাবে দেখানো হয়েছে। গ্রিডটি স্ট্রিং অ্যারে আকারে দেওয়া আছে। এখন আমাদের নিচের কাজগুলো করতে হবে:

যে সাদা কক্ষগুলো কালো কক্ষের পাশে থাকে (খাড়া বা দাঁড়ি দিক থেকে), সেগুলো কালো কক্ষে রূপান্তর করুন। এই অপারেশনটি তখন পর্যন্ত চালান যেতে না করেই গ্রিডের সব কক্ষ কালো হয়ে যায়।
গ্রিডের সব কক্ষ কালো করতে কতটি ইটারেশন লাগে তা গণনা করুন। গ্রিডের आरম্ভে কমপক্ষে একটি কালো কক্ষ থাকতে হবে।

যেমন, ইনপুট হলে h = 4, w = 4, grid = {"#...", ".#.." , "....", "...#"}

#	.	.	.
.	#	.	.
.	.	.	.
.	.	.	#

তবে আউটপুট হবে 3।

সকল কক্ষ কালো করতে ৩টি ইটারেশন লাগে।

সমাধানের ধাপসমূহ

এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

dx অ্যারে সংজ্ঞায়িত করুন আকার: 4 := { 1, 0, -1, 0 } dy অ্যারে সংজ্ঞায়িত করুন আকার: 4 := { 0, 1, 0, -1 } একটি ২D distance অ্যারে সংজ্ঞায়িত করুন একটি q কিউ সংজ্ঞায়িত করুন যা ইন্টিজার পেয়ার ধারণ করবে i := 0 দিয়ে আরম্ভ করুন, i < h হলে, (i ১ বাড়িয়ে) করুন: for j := 0, j < w হলে, (j ১ বাড়িয়ে) করুন: if grid[i, j] == '#', তবে: distance[i, j] := 0 q-তে pair(i, j) যোগ করুন while (q খালি নয়), করুন: now := q-র প্রথম উপাদান q-র থেকে মুছুন dir := 0 থেকে ৩ পর্যন্ত: cx := now.first + dx[dir] cy := now.second + dy[dir] if cx < 0 বা cx >= h বা cy < 0 বা cy >= w, তবে: continue if distance[cx][cy] == -1, তবে: distance[cx][cy] := distance[now.first][now.second] + 1 q-তে pair(cx, cy) যোগ করুন ans := 0 i := 0 থেকে h-1 পর্যন্ত: j := 0 থেকে w-1 পর্যন্ত: ans := ans এবং distance[i][j] এর সর্বোচ্চ মান print(ans)

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:

#include <bits/stdc++.h> using namespace std; void solve(int h, int w, vector <string> grid){    int dx[4] = { 1, 0, -1, 0 };    int dy[4] = { 0, 1, 0, -1 };    vector<vector<int>> distance(h, vector<int>(w, -1));    queue<pair<int, int>> q;    for (int i = 0; i < h; i++) {       for (int j = 0; j < w; j++) {          if (grid[i][j] == '#') {             distance[i][j] = 0;             q.push(pair<int, int>(i,j));          }       }    }    while (!q.empty()) {       auto now = q.front();       q.pop();       for (int dir = 0; dir < 4; dir++) {          int cx = now.first + dx[dir];          int cy = now.second + dy[dir];          if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue;          if (distance[cx][cy] == -1) {             distance[cx][cy] = distance[now.first][now.second] + 1;             q.push(pair<int, int> (cx, cy));          }       }    }    int ans = 0; for (int i = 0; i < h; ++i) {       for (int j = 0; j < w; ++j) {          ans = max(ans, distance[i][j]);       }    }    cout << ans << endl; } int main() {    int h = 4, w = 4; vector<string> grid = {"#...", ".#.." , "....", "...#"}; solve(h, w, grid); return 0; }

ইনপুট

4, 4, {"#...", ".#.." , "....", "...#"}