LeetCode -- Maximal Square

public class Solution {
    public int MaximalSquare(char[,] matrix) {
        
        var row = matrix.GetLength(0);
        var col = matrix.GetLength(1);
        if(row < 2){
            if(row == 0){
				return 0;
			}
			else if(col == 1){
				return matrix[0,0] == ‘1‘ ? 1 : 0;
			}
        }
        var max = 0;
		
        var dp = new int[row, col];
        for(var i = 0;i < row; i++){
            var x = matrix[i,0] == ‘1‘ ? 1 : 0;
			dp[i, 0] = x;
			
			if(dp[i,0] > max){max = dp[i,0];}
        }
        for(var i = 0;i < col; i++){
            var x = matrix[0,i] == ‘1‘ ? 1 : 0;
			dp[0, i] = x;
			if(dp[0,i] > max){max = dp[0,i];}
        }
        
        for(var i = 1;i < row; i++){
            for(var j = 1;j < col; j++){
				// neighbours all equals 1
                if(matrix[i,j] == ‘1‘ && dp[i-1,j] == 1 && dp[i, j-1] == 1 && dp[i-1,j-1] == 1){
					if(dp[i-1, j] == 1){
						dp[i,j] = 4;
					}
                }
				// neighbours all bigger than 1 and equals each other
				else if(matrix[i,j] == ‘1‘ && dp[i-1,j] == dp[i,j-1] && dp[i-1,j-1] == dp[i-1,j] && dp[i-1,j] > 1){
					dp[i,j] = (int)Math.Pow(Math.Sqrt(dp[i,j-1]) + 1,2);
				}
				// neighbours all no less than 1, but may not equals each other
				else if(matrix[i,j] == ‘1‘ && dp[i-1,j] >= 1 && dp[i,j-1] >= 1 && dp[i-1,j-1] >= 1){
					var min = Math.Min(Math.Min(dp[i-1,j-1], dp[i-1,j]), dp[i,j-1]);
					dp[i,j] = (int)Math.Pow(Math.Sqrt(min) + 1,2);
				}
                else{
                    dp[i,j] = matrix[i,j] == ‘1‘ ? 1 : 0;
                }
				
				if(dp[i,j] > max){max = dp[i,j];}
            }
        }
		
        return max;
        
    }
}

LeetCode -- Maximal Square

原文：http://blog.csdn.net/lan_liang/article/details/48897063