Square Detector

SquareDetector.cpp

#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <climits>
#include <cstdio>

using namespace std;

bool detect(vector<string> square) {
    typedef pair<int, int> point_t;
    const int m = square.size();
    const int n = square[0].size();
    point_t left_top, right_bottom;

    // find the first '#' as left top
    bool left_top_found = false;
    for (int i = 0; i < m && !left_top_found; ++i) {
        for (int j = 0; j < n; ++j) {
            if (square[i][j] == '#') {
                left_top.first = i;
                left_top.second = j;
                left_top_found = true;
                break;
            }
        }
    }
    // find right bottom
    point_t white = make_pair(INT_MAX, INT_MAX); // 记录黑色方阵中，最左上的白点
    for (int i = left_top.first; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (square[i][j] == '#') {
                if (j < left_top.second) return false;

                right_bottom.first = i;
                right_bottom.second = j;

                if (white.first <= right_bottom.first && white.second <= right_bottom.second) 
                    return false;
            }
            else {
                if (j >= left_top.second && white.first == INT_MAX) {
                    white.first = i;
                    white.second = j;
                }
            }
        }
    }

    return right_bottom.first - left_top.first == right_bottom.second - left_top.second;
}


int main() {
    freopen("square_detector.txt", "r", stdin);
    freopen("square_detector_out.txt", "w", stdout);
    int T;
    cin >> T;
    int case_no = 0;
    while (T-- > 0) {
        ++case_no;
        int N;
        cin >> N;
        vector<string> square;
        for (int i = 0; i < N; ++i) {
            string str;
            cin >> str;
            square.push_back(str);
        }

        if (detect(square)) {
            cout << "Case #" << case_no << ": YES" << endl;
        }
        else {
            cout << "Case #" << case_no << ": NO" << endl;
        }
    }
}