164. 最大正方形

Task Description
最大正方形
給定一組 m 列 n 行的二維陣列 a ， a 中元素只有0跟1。請在 a 中找出只包含1的最大正方形面積。

Hint

正方形邊長要變大必須是當前位置、上、左和左上都為1時，邊長就會加1
但4個位置如果不全部是1，就表示邊長不增加
因此就可以建立一個表紀錄邊長大小
例如輸入陣列是 :
1 1 0
1 1 1
0 0 1
建立表格就是
1 1 0
1 2 1
0 0 1

MaximalSquare.h

打上 function header 以及相關的設定。

void findMaximalSquare(int** matrix, int rows, int cols, int *maxEdge);

MaximalSquare.c

撰寫程式碼後對應上傳。

#include "MaximalSquare.h"
 
void findMaximalSquare(int** matrix, int rows, int cols, int *maxEdge) {
    / add your code /
}

main.c

這個檔案無法更改也無須上傳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
#include "MaximalSquare.h"
 
int main() {
    int row, col;
    scanf("%d %d", &row, &col);
    int** matrix = (int**)malloc(row * sizeof(int*));
    int i, j, tmp;
    for (i = 0; i < row; i++) {
        matrix[i] = (int*)malloc(col * sizeof(int));
    }
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            scanf("%d", &tmp);
            matrix[i][j] = tmp;
        }
    }
 
    int maxEdge = 0;
    findMaximalSquare(matrix, row - 1, col - 1, &maxEdge);
 
    printf("%d", maxEdge * maxEdge);
    for (i = 0; i < row; i++) {
        free(matrix[i]);
    }
    free(matrix);
 
}

Input Format

第一列輸入為 m、n ，第2列至第 m+1 列為 a 中的 n 個元素值。
Note: 0<m、n≤15、0≤a[i][j]≤1

Output Format

輸出最大正方形面積

Sample Input

1
2
3
4
5
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Sample Output

1
4

Sample Input

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

Sample Output

1
4