You are viewing a single comment's thread. Return to all 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;}
Seems like cookies are disabled on this browser, please enable them to open this website
Connected Cells in a Grid
You are viewing a single comment's thread. Return to all comments →
**My Solution in C++ **
PS: I didn't know DFS so I came out with my own approach
Code: