LintCode 897. Island City - Weekly9

http://www.lintcode.com/en/problem/island-city/

You could use UnionFind, I just don't bother doing it.

As the islands are not dynamic UnionFind is unnecessary.

Just use plain old DFS, trigger it with a simple scan for cities that's not visited, then paint all visited cities with 2(or maybe not, it doesn't matter now).

Then count the number of triggers.

Boom!

	public class Solution {
	/**
	* @param grid: an integer matrix
	* @return: an integer
	*/
	int numIslandCities(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	this.A = A;
	this.visited = new boolean[m][n];
	int counter = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (A[i][j] == 2 && !visited[i][j]) {
	dfs(i, j);
	counter++;
	}
	}
	}
	// return the final result
	return counter;
	}
	int[][] A;
	boolean[][] visited;
	int m;
	int n;
	private void dfs(int i, int j) {
	if (i < 0 || j < 0 || i >= m || j >= n) {
	return;
	}
	if (A[i][j] == 0) {
	return;
	}
	if (visited[i][j]) {
	return;
	}
	visited[i][j] = true;
	A[i][j] = 2;
	dfs(i - 1, j);
	dfs(i + 1, j);
	dfs(i, j - 1);
	dfs(i, j + 1);
	}
	}

view raw LintCode 897. Island City - Weekly9 - LintCode.java hosted with ❤ by GitHub