Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Given an N x M matrix of all 1s and 0s, find the largest submatrix which is a square containing all 1s.

Input 

There will be several test cases in the input. Each test case will begin with two integers, N and M (1N, M1, 000) indicating the number of rows and columns of the matrix. The next N lines will each contain M space-separated integers, guaranteed to be either 0 or 1. The input will end with a line with two 0s.

Output 

For each test case, print a single integer, indicating the width (and height) of the largest square of all 1s, or 0 if there are no 1s. Print no extra spaces, and do not print any blank lines between answers.

Sample Input 

4 5 
0 1 0 1 1 
1 1 1 1 1 
0 1 1 1 0 
1 1 1 1 1 
3 4 
1 1 1 1 
1 1 1 1 
1 1 1 1 
6 6 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0

Sample Output 

3 
3 
0

---

求最大矩形, DP 方法找到左, 左上, 上 方的最大矩形, 三者的最小值+1 

#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, m;
    int i, j, A[1001], B[1001];
    while(scanf("%d %d", &n, &m) == 2) {
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        if(n == 0 && m == 0)
            break;
        int *ta = A, *tb = B, *tc;
        int ans = 0, x, t;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                ReadInt(&x);
                if(x) {
                    ta[j] = ta[j-1];
                    ta[j] = min(ta[j], tb[j-1]);
                    ta[j] = min(ta[j], tb[j]);
                    ta[j]++;
                    if(ta[j] > ans)
                        ans = ta[j];
                } else
                    ta[j] = 0;
            }
            tc = ta, ta = tb, tb = tc;
        }
        printf("%d\n", ans);
    }
    return 0;
}