本文主要是介绍find the largest subsquare surrounded by ‘w’ 和‘W’，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一个char[][] board，里面有‘b’'B''w''W'四种，bB都表示black，wW都表示white，找最大的正方形面积，这个正方形四个边都是black，正方形中间随便黑白无所谓。Example：一个5x5的board如下，符合条件最大正方形是个3x3的，return面积9。
wwbww
wbbbb
bbWbw
Bbbbb
wwwww
参考：点击打开链接
public static void main(String[] args) {int mat1[][] = { { 'b', 'w', 'b', 'b', 'b', 'b' }, { 'b', 'w', 'b', 'b', 'w', 'b' },{ 'b', 'b', 'b', 'w', 'w', 'b' }, { 'w', 'b', 'b', 'b', 'b', 'b' },{ 'b', 'b', 'b', 'w', 'b', 'w' }, { 'w', 'w', 'b', 'w', 'w', 'w' } };int len = findSubSquare(mat1);System.out.println(len);int mat2[][] = { { 'w', 'w', 'b', 'w', 'w' }, { 'w', 'b', 'b', 'b', 'b' },{ 'b', 'b', 'w', 'b', 'w' }, { 'B', 'b', 'b', 'b', 'b' },{ 'w', 'w', 'w', 'w', 'w', 'w' } };len = findSubSquare(mat2);System.out.println(len);}static int getMin(int x, int y) {return (x < y) ? x : y;}// Returns size of maximum size subsquare matrix// surrounded by 'X'static int findSubSquare(int mat[][]) {int max = 1; // Initialize resultint len = mat.length;// Initialize the left-top value in hor[][] and ver[][]int[][] hor = new int[len][len];int[][] ver = new int[len][len];// Fill values in hor[][] and ver[][]for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {if (mat[i][j] == 'w' || mat[i][j] == 'W')ver[i][j] = hor[i][j] = 0;else {hor[i][j] = (j == 0) ? 1 : hor[i][j - 1] + 1;ver[i][j] = (i == 0) ? 1 : ver[i - 1][j] + 1;}}}// Start from the rightmost-bottommost corner element and find// the largest ssubsquare with the help of hor[][] and ver[][]for (int i = len - 1; i >= 1; i--) {for (int j = len - 1; j >= 1; j--) {// Find smaller of values in hor[][] and ver[][]// A Square can only be made by taking smaller// valueint small = getMin(hor[i][j], ver[i][j]);// At this point, we are sure that there is a right// vertical line and bottom horizontal line of length// at least 'small'.// We found a bigger square if following conditions// are met:// 1)If side of square is greater than max.// 2)There is a left vertical line of length >= 'small'// 3)There is a top horizontal line of length >= 'small'while (small > max) {if (ver[i][j - small + 1] >= small && hor[i - small + 1][j] >= small) {max = small;}small--;}}}return max;}这篇关于find the largest subsquare surrounded by ‘w’ 和‘W’的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
