stol.cpp

Bài toán

Ta có thể phát biểu lại bài toán thành: Cho một ma trận m x n, các ô có thể là dấu chấm '.' hoặc dấu thăng '#'. Tìm chu vi lớn nhất của hình chữ nhật mà chỉ chứa dấu chấm rồi trừ đi 1.

Độ phức tạp

O(m*n*(m+n))

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }

int m, n;

char a[456][456];

int s[456][456];

int answer=0;

int sum(int x, int y, int xx, int yy){

    if (xx>m or yy>n) return 1;

    int r = s[xx][yy]-s[x][yy]-s[xx][y]+s[x][y];

    //printf("sum(%d, %d, %d, %d = %d\n", x, y, xx, yy, r);

    return r;

}

void optimize(int x, int y){

    //printf("optimize(%d, %d)\n", x, y);

    int i=x;

    int j=n;

    while (i<=m){

        if (i==x || j==y) i++;

        else if (sum(x,y,i,j)==0) {

            maximize(answer, (i-x)+(j-y));

            i++;

        }

        else j--;

    }

}

main(){

    int i, j;

    scanf ("%d%d", &m, &n);

    for (i=1; i<=m; i++)

    scanf("%s", a[i]+1);

    for (i=1; i<=m; i++)

    for (j=1; j<=n; j++)

    s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]-'.';

    for (i=1; i<=m; i++)

    for (j=1; j<=n; j++)

    optimize(i-1, j-1);

    printf("%d\n", answer+answer-1);

}

Nhận xét

Giả sử ta đã xác định góc trái trên của hình chữ nhật là (x0,y0). Ta có thể xác định được góc phải dưới (x,y) với độ phức tạp O(m+n). Ta sẽ cho x=m, y=y0, lặp lại quá trình này liên tục đến khi y>n: nếu hình chữ nhật (x0,y0,x,y) hợp lệ, ta tăng y, ngược lại, ta giảm x.