We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Connected Cells in a Grid
Connected Cells in a Grid
+ 0 comments Ruby:
def cover_neighbours(i,j,m,n) return if i>=n || j>=m || i<0 || j<0 return if @matrix[i][j] == 0 @matrix[i][j] = 0 @count += 1 cover_neighbours(i+1,j,m,n) cover_neighbours(i-1,j,m,n) cover_neighbours(i,j+1,m,n) cover_neighbours(i,j-1,m,n) cover_neighbours(i+1,j-1,m,n) cover_neighbours(i-1,j+1,m,n) cover_neighbours(i+1,j+1,m,n) cover_neighbours(i-1,j-1,m,n) end def connectedCell(matrix) n = matrix.size m = matrix[0].size @matrix = matrix max_count = 0 for i in 0..(n-1) do for j in 0..(m-1) do if @matrix[i][j] == 1 @count = 0 cover_neighbours(i,j,m,n) max_count = @count if @count > max_count end end end return max_count end
+ 0 comments **My Solution in C++ **
PS: I didn't know DFS so I came out with my own approach
Code:
#include <bits/stdc++.h> using namespace std; #define printTime(t) cout << "\nTIME: " << (float) t/CLOCKS_PER_SEC << "\n"; typedef long long ll; #define F first #define S second typedef vector<int> vi; #define pop_front() erase(0,1); const int mod = 1e9 + 7; int visited[10][10]; vector<vector<int>> matrix(10,vector<int> (10,0)); int ni, mi; int search(int i ,int j){ int result = 1; visited[i][j] = 1; bool l, r, d, ld,rd, u,lu,ru; l = (j-1 >= 0) && (matrix[i][j-1]) ; r = (j+1 < mi) && (matrix[i][j+1]) ; ld = (j-1 >= 0 && i+1 < ni) && (matrix[i+1][j-1]); rd = (j+1 < mi && i+1 < ni) && (matrix[i+1][j+1]); d = (i+1 < ni) && (matrix[i+1][j]); u = (i-1 >= 0) && (matrix[i-1][j]); lu = (i-1 >= 0 && j-1 >= 0) && (matrix[i-1][j-1]); ru = (i-1 >= 0 && j+1 < mi) && (matrix[i-1][j+1]); if(l && !visited[i][j-1]){ result += search(i,j-1); } if(r && !visited[i][j+1]){ result += search(i,j+1); } if(d && !visited[i+1][j]){ result += search(i+1,j); } if(ld && !visited[i+1][j-1]){ result += search(i+1,j-1); } if(rd && !visited[i+1][j+1]){ result += search(i+1,j+1); } if(u && !visited[i-1][j]) { result += search(i-1, j); } if(lu && !visited[i-1][j-1]) { result += search(i-1, j-1); } if(ru && !visited[i-1][j+1]) { result += search(i-1, j+1); } return result; } int connectedCell(vector<vector<int>> matrix) { int count = INT_MIN; for(int i = 0; i < ni; i++){ for(int j = 0; j < mi; j++){ if(!visited[i][j] && matrix[i][j]){ int temp = search(i,j); count = max(count, temp); // printf("[%d, %d] | %d\n",i,j,temp); // cout << "[" << i << ","<<j<<"] | "<<temp << '\n'; } } } return count; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int t = 1, n, m,k; //cin >> t; while(t--){ cin >> ni >> mi; for(int i = 0; i < ni; i++){ for(int j = 0; j < mi ; j++) cin >> matrix[i][j]; } cout << connectedCell(matrix) << endl << endl; // for(int i = 0; i < ni; i++) // { // for(int j = 0; j < mi; j++) // cout << visited[i][j] << ' '; // cout << endl; // } } return 0;}
+ 0 comments Here is my solution in java, javascript, python, C, C++, Csharp Click Here
+ 0 comments BFS
#include<bits/stdc++.h> using namespace std; #define ROW 10 #define COL 10 int n, m; int grid[ROW][COL]; bool vis[ROW][COL]; int ans = 0; // Direction vectors vector<vector<int>> dir{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}; // Function to check if a cell is be visited or not bool isValid(bool vis[][COL], int row, int col){ if (row < 0 || row >= ROW || col < 0 || col >= COL) return false; if (vis[row][col]) return false; return true; } // Function to perform the BFS void BFS(int grid[][COL], bool vis[][COL], int row, int col){ int tem = 0; queue<pair<int, int>> q; q.push({row, col}); vis[row][col] = true; while (!q.empty()){ pair<int, int> fro = q.front(); int x = fro.first; int y = fro.second; q.pop(); tem++; for (auto d : dir){ int neix = x + d[0]; int neiy = y + d[1]; if (isValid(vis, neix, neiy) && grid[neix][neiy]){ q.push({neix, neiy}); vis[neix][neiy] = true; grid[neix][neiy] = 0; } } } ans = max(ans, tem); } // Driver code int main(){ cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> grid[i][j]; memset(vis, false, sizeof(vis)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j]) BFS(grid, vis, i, j); cout << ans; }
+ 1 comment Here's a simple solution Go:
func rSearch(matrix *[][]int32, r, c, rows, cols int32) int32 { sum := int32(1) (*matrix)[r][c] = int32(2) // mark cell as visited for i := int32(-1); i <= 1; i++ { for j := int32(-1); j <= 1; j++ { if (i == 0 && j == 0) || r + i < 0 || r + i >= rows || c + j < 0 || c + j >= cols { continue } if (*matrix)[r+i][c+j] == 1 { sum += rSearch(matrix, r + i, c + j, rows, cols) } } } return sum } func connectedCell(matrix [][]int32) int32 { // - iterate over matrix left to right top to bottom // - when finding a cell, recursively explore the unvisited neighbors rows := int32(len(matrix)) cols := int32(len(matrix[0])) var mSize int32 for r := int32(0); r < rows; r++ { for c := int32(0); c < cols; c++ { if matrix[r][c] == 1 { size := rSearch(&matrix, r, c, rows, cols) if size > mSize { mSize = size } } } } return mSize }
Load more conversations
Sort 247 Discussions, By:
Please Login in order to post a comment