rectangles.cpp

/*
    File: rectangles.cpp

    Compile command: g++ -O2 -std=c++17 -Wall -Wextra -pedantic rectangles.cpp -o rectangles.o

    Example:
    4 3
    ###
    #.#
    #.#
    ###

    Output: 1
*/


#pragma GCC diagnostic ignored "-Wunused-result"
#include <stdio.h>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <cstdint>

const bool TIMING = false;

char getChar() {
    static char buffer[1024*1024];
    static int pos = 0;
    static int size = 0;
    if (pos == size) {
        size = fread(buffer, 1, 1024*1024, stdin);
        pos = 0;
    }
    if (pos == size) {
        return EOF;
    }
    return buffer[pos++];
}

void putChar(char c) {
// c == -1 or size == sizeof(buffer) --> flush buffer
    static char buffer[1024*1024];
    static int size = 0;
    if (size == 1024 * 1024 || c == -1) {
        fwrite(buffer, 1, size, stdout);
        size = 0;
    }
    buffer[size++] = c;
}

int getInt(bool& success) {
    char c = '?';
    while (!(c == '-' || ('0' <= c && c <= '9') || c == EOF)) {
        c = getChar();
    }
    if (c == EOF) {
        success = false;
        return 0;
    }
    int sign = 1;
    if (c == '-') {
        sign *= -1;
        c = getChar();
    }
    int answ = 0;
    while ('0' <= c && c <= '9') {
        (answ *= 10) += (c-'0');
        c = getChar();
    }
    success = true;
    return sign * answ;
}

void putStr(const char *buf) {
    for (auto it = buf; *it != '\0'; ++it) {
        putChar(*it);
    }
}

void putInt(int number) {
    static char buf[12];
    sprintf(buf, "%d", number);
    putStr(buf);
}

void putInt(long long number) {
    static char buf[24];
    sprintf(buf, "%lld", number);
    putStr(buf);
}

int main() {
    double total_time = clock();
    while (true) {
        bool flag;
        int nRows = getInt(flag); // input number of rows of array
        int nCols = getInt(flag); // input number of cols of array
        if (!flag) {
            break;
        }
        static char arr[350][350]; // arr[r][c] = 1 if '#' and arr[r][c] = 0 if '.'
        for (int row = 0; row < nRows; ++row) {
            for (int col = 0; col < nCols; ++col) {
                char c = getChar();
                arr[row][col] = (c == '#');
            }
            char c = getChar();
            assert(c == '\n' || (c == EOF && row == nRows-1));
        }

        static int maxLenDown[351][350]; // maxLenDown[r][c] = len of max sequence of '#' from pos (row, col) in side of increasing row
        for (int row = 0; row <= nRows; ++row) {
            for (int col = 0; col < nCols; ++col) {
                maxLenDown[row][col] = 0;
            }
        }

        for (int row = nRows-1; row >= 0; --row) {
            for (int col = 0; col < nCols; ++col) {
                if (arr[row][col]) {
                    maxLenDown[row][col] = 1 + maxLenDown[row+1][col];
                }
            }
        }

        static int bin_2[351]; // bin_2[i] = C(i, 2);
        for (int i = 0; i < 351; ++i) {
            bin_2[i] = i * (i-1) / 2;
        }

        // Calculate all rectangles with top side = row1 and bottom side = row2 (rectangles with width = 2 will also be counted)
        long long answ = 0;
        for (int row1 = 0; row1 < nRows-2; ++row1) {
            int temp = 0;
            for (int row2 = row1+2; row2 < nRows; ++row2) {
                int len = 0;
                for (int col = 0; col < nCols; ++col) { // TO DO: speed up this cycle
                    if (arr[row1][col] & arr[row2][col]) {
                        len += (maxLenDown[row1][col] >= row2-row1+1);
                    } else {
                        temp += bin_2[len];
                        len = 0;
                    }
                }
                temp += bin_2[len];
            }
            answ += temp;
        }
        // Decreasing number of rectangles with width = 2
        for (int col1 = 0; col1 < nCols-1; ++col1) {
            const int col2 = col1+1;
            int len = 0;
            for (int row = 0; row < nRows; ++row) {
                if (arr[row][col1] & arr[row][col2]) {
                    ++len;
                } else {
                    if (len >= 3) {
                        answ -= bin_2[len-1];
                    }
                    len = 0;
                }
            }
            if (len >= 3) {
                answ -= bin_2[len-1];
            }
        }

        putInt(answ);
        putChar('\n');
    }
    putChar(-1);

    if (TIMING) {
        total_time = (clock() - total_time) / CLOCKS_PER_SEC;
        printf("----------------\ntime = %0.3f\n", total_time);
    }

    return 0;
}