Flood Fill

The idea is to find the node that has not been assigned to a component. Flood fill can be performed in two ways, both O(N+M):

• depth-first: assign unvisited neighbors to the current component and recurses on them.
• breadth-first: no recursion, all the unvisited neighbors are push onto a queue.

Problems:

UVa 352: The Seasonal War

int dx[] = {-1, 0, 0, 1, 1, -1, 1, -1};
int dy[] = {0 , -1,1, 0, 1, -1, -1, 1};

void visit(vector<vector<int> > &V, vector<string> &M, int i, int j) {
	int N = V.size();
	if(i < 0 || i >= N || j < 0 || j >= N) return ;

	// '0' pixel or  visited already
	if(M[i][j] == '0' || V[i][j] > 0) return ;
	
	V[i][j] = 1; 
	for(int k = 0; k < 8; ++k)
		visit(V, M, i+dx[k], j+dy[k]);
	return; 
}

int flood_fill(vector<string> &M) {
	int N = M.size();
	vector<vector<int> > V(N, vector<int>(N, -1));
	
	int ncomp = 0; // number of components
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j) {
			// the pixel contains "1" and it has not been visited
			if(M[i][j] == '1' && V[i][j] == -1) {
				ncomp ++;
				for(int k = 0; k < 8; ++k)
					visit(V, M, i+dx[k], j+dy[k]);
			}
		}
    return ncomp;
}

UVa 572: Oil Deposits

topCoder: HoleCakeCuts 

Editorial:

Approach 1

Flood-filling by Depth-first search (DFS) or Breadth-first search (BFS) is used to count the number of pieces. The cake can be divided into many unit squares (each has a side length of 1), and a piece is a maximal connected group of unit squares which has the property that no common border (if existing) between any two squares in the group lies on a cut. So from a unit square of some piece we can visit all other unit squares belonging to that piece by limiting DFS or BFS not to cross any cut while travelling between squares. See Petr's solution for a clean implementation of this approach.

Approach 3

Another approach which has a smaller time complexity is to reduce the original problem to a problem with a cake and no hole. This can be done by finding two horizontal cuts:

1. the horizontal cut which is inside the hole and closest to the top side of the hole. It can be the cut going through the top side of the hole.


2. the horizontal cut which is inside the hole and closest to the bottom side of the hole. It can be the cut going through the bottom side of the hole.

These two cuts (which may be the same cut) together with the vertical sides of the hole divide the outer square of the cake into four rectangles each of which can be considered as a cake with no hole. The fifth rectangle in the center always contains no pieces. The four rectangles are colored differently in the following illustration:

If the two horizontal cuts of interest cannot be found, we can search for two vertical cuts with similar properties. And if, again, we cannot find the cuts, we can safely remove the hole from the original cake to obtain a reduced problem.

Solving a reduced problem is trivial. We just count the numbers of horizontal and vertical cuts which completely cut through the cake (not going through any border of the cake), add one to each number, and then multiply them together to get the number of pieces.