首页 > 代码库 > CC150 20.11
CC150 20.11
20.11 Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
// A brute force solution. // n * n // iterate from n to 1. // For n, find all possible sub square Enum Color { BLACK, WHITE; } // Check sub square (left-up point [row][col], length) has all borders black // Assume square is not null, N * N matrix (N >= 1) // row and col >= 0 // row + len < square.length // col + len < square.length boolean hasBlackBorders(Color[][] square, int row, int col, int len) { for (int i = 0 ; i < len ; i ++) { if (square[row + i][col] != BLACK) // left return false; if (square[row + i][col + len - 1] != BLACK) // right return false; if (square[row][col + i] != BLACK) // up return false; if (square[row + len - 1][col + i] != BLACK) // up return false; } return true; } // O(n^) void maxSubSquareWithBlackBorders(Color[][] square) { int maxLen = square.length; for (int len = maxLen ; len > 0 ; len --) { // Given len, find possible left-up start for (int row = 0 ; row < maxLen - len + 1 ; row ++) { for (int col = 0 ; col < maxLen - len + 1 ; col ++) { if (hasBlackBorders(square, row, col, len)) { // Return the sub square with left-up point[row][col], and len. return; } } } } return null; } // A better solution? class Node { Color color; Integer maxDownRight; Integer maxUpLeft; boolean hasMaxDownRight(); } // O(n) // Populate the max down/right this node can go. void populateDownRight(Node[][] square, int row, int col) { int maxLen = square.len; if (square[row][col].color == WHITE) return; int down = 0; if (row > 0 && square[row - 1][col].hasDownRight()) down = square[row - 1][col].downRight - 1; else { for (int = row + 1 ; i < maxLen ; i ++) { down ++; } } int right = 0; // Similar to calculate down square[row][col].downRight = min(down, right); } // void populateUpLeft(Node[][] square, int row, int col) // Similar to populateDownRight O(n ^ 3) void maxSubSquareWithBlackBorders(Node[][] square) { // Populate down right for (int i = 0 ; i < maxLen ; i ++) { for (int j = 0 ; j < maxLen ; j ++) { populateDownRight(i, j); } } // Populate up left for (int i = 0 ; i < maxLen ; i ++) { for (int j = 0 ; j < maxLen ; j ++) { populateUpLeft(maxLen - i, maxLen - j); } } // Find maxOne. Node toReturn; int maxLenSeen = -1; for (int i = 0 ; i < maxLen ; i ++) { for (int j = 0 ; j < maxLen ; j ++) { int downRight = square[i][j].downRight; int possibleSqureUpLeft = square[i + downRight][j + downRight].upLeft; if (possibleSqureUpLeft >= downRight) { // We find a square matching. if (downRight > maxLenSeen) { toReturn = square[i][j]; maxLenSeen = downRight; } } } // Print toReturn with maxLenSeen. } }
CC150 20.11
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。