找最大方阵

本文主要是介绍找最大方阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://haixiaoyang.wordpress.com/category/dynamic-programming/

这个比求最大矩阵要方便多了，记录的是rec[i][j]矩阵边上的点的数目

//There is a square of n x n size which is comprised of n-square 1x1 squares. 
//Some of these 1x1 squares are colored. Find the biggest 
//sub square which is colored.  Also asked to extend it to find the biggest area rectangleconst int N = 5;
int FindLargestArea(bool A[N][N])
{int rec[N][N];int nRet = 0;for (int i = 0; i < N; i++){rec[0][i] = A[0][i] ? 1 : 0;if (rec[0][i] > nRet)nRet = rec[0][i];}for (int i = 0; i < N; i++){rec[i][0] = A[i][0] ? 1 : 0;if (rec[i][0] > nRet)nRet = rec[i][0];}for (int i = 1; i < N; i++){for (int j = 1; j < N; j++){if (!A[i][j]){rec[i][j] = 0;continue;}rec[i][j] = 1 + min(min(rec[i][j-1], rec[i-1][j]), rec[i-1][j-1]);//this is the first logic I write/*if (rec[i][j-1] == 0 || rec[i-1][j] == 0)rec[i][j] = 1;else{int nTmp = min(rec[i][j-1], rec[i-1][j]);//well, I missed the brackets leading to errorsrec[i][j] = nTmp + (A[i-nTmp][j-nTmp] ? 1 : 0);}*/if (rec[i][j] > nRet)nRet = rec[i][j];}}return nRet;
}

这篇关于找最大方阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---