ACM 836 Largest Submatrix

我的辦法是利用解二維Maximum Consecutive Sum的辦法：

只要把0視為一個負無限大的數字，接著再用108的辦法，就能找出最大的長方形區域
所以只要把108的Code拿來改一改就可以AC了
但是要注意n=1的情況，讀取輸入的部分寫不好的話會讓n=1測資之後的測資讀取輸入都出問題

我總覺得應該有更好的辦法......


 #include <stdio.h>

#define N 25

int arr[N][N];

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int max_subarr(int * arr, int n)
{
    int i, max, sum;
 
    sum = max = 0;
    for (i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum < 0)
            sum = 0;
        else
            if (sum > max)
                max = sum;
    }
 
    return max;
}

int main(void)
{
    int i, j, k, n, t, tmp, M, sum[N], flag = 0;
    char ch;
  
    scanf("%d", &t);  
    while (t--)
    {
        // 讀取輸入
        while ((ch = getchar()) == '\n')
            continue;
        if (ch == '1')
            arr[0][0] = 1;
        else
            arr[0][0] = -1000;  // 把0視為負無限大 (設定的值必須<= -625)
        n = 1;
        while ((ch = getchar()) != '\n')
        {
            if (ch == '1')
                arr[0][n++] = 1;
            else
                arr[0][n++] = -1000;
        }
        for (i = 1; i < n; i++)
            for (j = 0; j < n; j++)
            {
                scanf("%1d", &tmp);
                if (tmp)
                    arr[i][j] = 1;
                else
                    arr[i][j] = -1000;
            }
      
        // 計算2 Dimensional Maximum Consecutive Sum
        M = 0;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
                sum[j] = arr[i][j];
            tmp = max_subarr(sum, n);
            M = max(tmp, M);
            for (j = i+1; j < n; j++)
            {
                for (k = 0; k < n; k++)
                    sum[k] += arr[j][k];
                tmp = max_subarr(sum, n);
                M = max(tmp, M);
            }
        }
        if (flag)
            printf("\n");
        else
            flag = 1;
        printf("%d\n", M);
    }
  
    return 0;
}