Think about problem, what does the problem wants? We have a grid and we want to find the number of connected components in this grid, the largest component before breaking a wall, and the largest component after breaking a wall, we also need the wall itself.
To find connected components one can easily use DFS.
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
To deal with neighbors I have this array 'dir', a[i][j] is the value of cell (i, j), I want to know whether I can go to the other cells connected to (i, j) or not.
After DFS, I iterate over cells as the problem statement wants and check it's neighbors, if its neighbor is in another component I check the size of the merged component to the maximum size found.
To find connected components one can easily use DFS.
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
To deal with neighbors I have this array 'dir', a[i][j] is the value of cell (i, j), I want to know whether I can go to the other cells connected to (i, j) or not.
After DFS, I iterate over cells as the problem statement wants and check it's neighbors, if its neighbor is in another component I check the size of the merged component to the maximum size found.
No comments:
Post a Comment