Java

gistfile1.txt

public class Challenge352 {
	static int sum, squares;
	static int pmin, min, minr, minc;
	static int target;
	static boolean found;
	
	static int dir[][] = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
	
	static int main(int N, int[][] matrix, int M) {
		int[] start = getStart(N, matrix);
		sum = 0; squares = 0; pmin = M; min = M;
		minr = start[0]; minc = start[1]; target = M;
		found = false;
		
		while(!found)
		{
			sum += squares*(min - pmin);	//Fill up all visited squares to the next square
			pmin = min;
			min = Integer.MAX_VALUE;
			dfs(N, matrix, minr, minc, pmin);	//DFS from that visited square or starting square 1
		}
		if(pmin > target)
			return sum+1;
		else
		{
			squares++; // Must fill up squares + target square by 1 unit
			return sum+squares; // Which takes 1 unit of time each
		}
	}
	static void dfs(int N, int[][] matrix, int r, int c, int end) {
		if(matrix[r][c] == -1) return;
		if(matrix[r][c] == target)	//We found the target
		{
			found = true;
			return;
		}
		if(matrix[r][c] > end)
		{
			if(matrix[r][c] < min)	//Find next smallest square that isn't filled
			{
				min = matrix[r][c];
				minr = r;
				minc = c;
			}
			return;
		}
		
		//Fill the square and keep count of filled/visited squares
		sum += (end - matrix[r][c]);
		squares++;
		matrix[r][c] = -1;

		for(int[] d : dir) //DFS neighbors
		{
			int nr = r + d[0];
			int nc = c + d[1];
			if(nr < 0 || nr >= N || nc < 0 || nc >= N)
				continue;
			dfs(N, matrix, nr, nc, end);
		}
	}
	
	//Find location of 1
	static int[] getStart(int N, int[][] matrix) {
		for(int r = 0; r < N; r++)
		{
			for(int c = 0; c < N; c++)
			{
				if(matrix[r][c] == 1)
					return new int[]{r,c};
			}
		}
		return new int[]{-1,-1};
	}
}