মান লেযিয়ে একটি ২D অ্যারে A দেওয়া আছে, যেখানে প্রতিটি সেল ০ (সমুদ্র) বা ১ (স্থল) উপস্থাপন করে। এখানে একটি মুভ হল একটি স্থল স্কোয়ার থেকে ৪-দিকaronder অন্য একটি স্থল স্কোয়ারে বা গ্রিডের বাউন্ডারি বাইরে যাওয়া। আমাদের গ্রিডে بتلك স্থল স্কোয়ারের সংখ্যা খুঁজে বের করতে হবে যারা থেকে যেকোনো সংখ্যক মুভ দিয়ে গ্রিডের বাউন্ডারি বাইরে যাওয়া সম্ভব নয়। গ্রিড যদি নিচের মতো হয় -
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
উত্তর হবে ৩, কারণ ০ দিয়ে ঘিরে ৩টি ১ আছে, আর ১টি ১ ঘেরা নয়।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি দিক অ্যারে dir তৈরি করুন, [[1,0], [-1,0], [0,1], [0,-1]] স্ট্রোর করুন
dfs() নামে একটি মেথড তৈরি করুন যা x, y এবং ম্যাট্রিক্স A নেবে
যদি x < 0 বা y < 0 বা x >= A.size() বা y >= A[0].size() বা A[x][y] == 0 হয়, রিটার্ন করুন
A[x][y] := 0 সেট করুন
k = 0 থেকে 3 পর্যন্ত লুপ চালান
nx := dir[k][0] + x, ny := dir[k][1] + y
dfs(nx, ny, A) কল করুন
মেইন মেথড থেকে - ret := 0, n := A.size()
m := n != 0 ? A[0].size() : 0
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
যদি A[i][0] == 1 হয়, dfs(i, 0, A) কল করুন
যদি A[i][m-1] == 1 হয়, dfs(i, m-1, A) কল করুন
i = 0 থেকে m-1 পর্যন্ত লুপ চালান
যদি A[0][i] == 1 হয়, dfs(0, i, A) কল করুন
যদি A[n-1][i] == 1 হয়, dfs(n-1, i, A) কল করুন
i = 0 থেকে n-1, j = 0 থেকে m-1 পর্যন্ত লুপ চালান
ret := ret + A[i][j]
return ret
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public: void dfs(int x, int y, vector < vector <int>>& A){ if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() || A[x][y] == 0) return; A[x][y] = 0; for(int k = 0; k < 4; k++){ int nx = dir[k][0] + x; int ny = dir[k][1] + y; dfs(nx, ny, A); } } int numEnclaves(vector<vector<int>>& A) { int ret = 0; int n = A.size(); int m = n ? A[0].size() : 0; for(int i = 0; i < n; i++){ if(A[i][0] == 1){ dfs(i, 0, A); } if(A[i][m - 1] == 1){ dfs(i, m - 1, A); } } for(int i = 0; i < m; i++){ if(A[0][i] == 1){ dfs(0, i, A); } if(A[n - 1][i] == 1){ dfs(n - 1, i, A); } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ ret += A[i][j]; } } return ret; } }; main(){ vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}; Solution ob; cout << (ob.numEnclaves(v1)); }ইনপুট
[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
আউটপুট
3
