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.
This was my timed solution. I am not very good a t matrix problems so if anyone could view my code and tell me why it may be abd or ugly or any improvements I'd greatly appreciate it!
int maxRegion(vector> grid) {
int max_region_amt = 0;
int n = grid.size();
int m = grid[0].size();
stack q;
vector visited(n*m);
int i = 0;
while(i < n * m){
if(grid[i / m][i % m]){
break;
}
visited[i] = true;
++i;
}
while (i < n*m && !visited[i]) {
visited[i] = true;
int amt_region = 1;
q.push(i);
cout << "New iteration: " << i << "\n";
while(q.size()){
int curr_value = q.top();
q.pop();
if(curr_value / m != 0){
int prev_row =(curr_value - m)/m;
if(!visited[curr_value - m]){
visited[curr_value - m] = true;
if(grid[prev_row][curr_value % m]){
q.push(curr_value - m);
amt_region++;
}
}
if(curr_value % m && !visited[curr_value - m - 1]){
visited[curr_value - m - 1] = true;;
if(grid[prev_row][curr_value % m -1]){
q.push(curr_value - m - 1);
amt_region++;
}
}
if((curr_value + 1) % m && !visited[curr_value - m + 1]){
visited[curr_value - m + 1] = true;;
if(grid[prev_row][curr_value % m +1]){
q.push(curr_value - m + 1);
amt_region++;
}
}
}
if(curr_value / m + 1 != n){
int next_row =(curr_value + m)/m;
if(!visited[curr_value + m]){
visited[curr_value + m] = true;
if(grid[next_row][curr_value % m]){
q.push(curr_value + m);
amt_region++;
}
}
if(curr_value % m && !visited[curr_value + m - 1]){
visited[curr_value + m - 1] = true;;
if(grid[next_row][curr_value % m - 1]){
q.push(curr_value + m - 1);
amt_region++;
}
}
if((curr_value + 1) % m && !visited[curr_value + m + 1]){
visited[curr_value + m + 1] = true;;
if(grid[next_row][curr_value % m +1]){
q.push(curr_value + m + 1);
amt_region++;
}
}
}
if((curr_value + 1) % m && !visited[curr_value + 1]){
visited[curr_value + 1] = true;;
if(grid[curr_value / m][curr_value % m +1]){
q.push(curr_value + 1);
amt_region++;
}
}
if((curr_value) % m && !visited[curr_value - 1]){
visited[curr_value - 1] = true;
if(grid[curr_value / m][curr_value % m - 1]){
q.push(curr_value +-1);
amt_region++;
}
}
while(i < n * m && (visited[i] || !grid[i / m][i % m])){
visited[i] = true;
++i;
}
}
max_region_amt = max(max_region_amt, amt_region);
}
cout << i << "\n";
return max_region_amt;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
DFS: Connected Cell in a Grid
You are viewing a single comment's thread. Return to all comments →
This was my timed solution. I am not very good a t matrix problems so if anyone could view my code and tell me why it may be abd or ugly or any improvements I'd greatly appreciate it!
int maxRegion(vector> grid) { int max_region_amt = 0; int n = grid.size(); int m = grid[0].size(); stack q; vector visited(n*m); int i = 0; while(i < n * m){
}