uva201

题目意思就是找正方形，思路是用两个矩阵存横向和纵向的线，遍历每个顶点，并且列举每个顶点存在的正方形。

#include <iostream>
#include<cstring>
using namespace std;
#define maxn 12
int h[maxn][maxn], v[maxn][maxn], sq[maxn], m, n;

void input();
int squares();
int check(int x, int y, int k);

int main() {
    int kase = 0;
    while (cin >> n) {
        cin >> m;
        input();
        int res = squares();
        if(kase)cout<<"
**********************************

";
        cout << "Problem #" << ++kase << endl<<endl;
        if (res) {
            for (int i = 1; i <= n; i++) {
                if (sq[i]) {
                    cout << sq[i] << " square (s) of size " << i << endl;
                }
            }
        } else {
            cout << "No completed squares can be found." << endl;
        }
    }
    return 0;
}

void input() {
    char cmd[5];
    int a, b;
    memset(h, 0, sizeof(h));
    memset(v, 0, sizeof(v));
    memset(sq, 0, sizeof(sq));
    for (int i = 0; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd[0] == 'H')
            h[a][b + 1] = 1;
        else
            v[b + 1][a] = 1;
    }
}

int squares() {
    int flag = 0, i, j, k;
    for (i = 1; i <= n - 1; i++)
        for (j = 1; j <= n - 1; j++)
            for (k = 1; k <= n - 1; k++) {
                if ((i + k <= n) && (j + k <= n)) {
                    if (check(i, j, k)) {
                        sq[k]++;
                        flag++;
                    }
                }
            }
    return flag;
}

int check(int x, int y, int k) {
    int res = 1;
    for (int i = y + 1; i <= y + k; i++)
        if ((h[x][i] == 0) || (h[x + k][i] == 0))
            res = 0;
    for (int i = x + 1; i <= x + k; i++)
        if ((v[i][y] == 0) || (v[i][y + k] == 0))
            res = 0;
    return res;
}