UVA - 201 Squares

UVA - 201 Squares

（1）把每相邻两点之间插入一个坐标表示边做一个2*n-1的map
（2）点之间的边用‘1’表示连接

---

#include"stdio.h"
#include"iostream"
#include"algorithm"
#include"string.h"
using namespace std;
char map[18][18];
int n, m;
bool isout(int x,int y,int i)
{
    if (x + i < 2 * n && y + i < 2 * n)return false;
    return true;
}
bool find(int l)
{
    int cnt = 0;
    for (int i = 1; i < 2 * n; i += 2)
    {
        for (int j = 1; j < 2 * n; j += 2)
        {
            int is = 1;
            int sq = 2 * l;
            if (isout(i, j, sq))continue;//正方形越界直接判断下一个点
            for (int k = 1; k < 2 * l; k += 2)
            {
                if (map[i][j + k] != '1' || map[i + k][j] != '1' || map[i + sq][j + k] != '1' || map[i + k][j + sq] != '1')
                {
                    is = 0; break;
                }
            }
            if (is)cnt++;
        }
    }
    if (cnt)
    {
        printf("%d square (s) of size %d\n", cnt, l);
        return true;
    }
    return false;
}
int main()
{
    int flag, time = 0;
    while (cin >> n >> m && ++time)
    {
        int x, y; char hv;
        memset(map, ' ', sizeof(map));
        /*for (int i = 1; i < 2 * n; i+=2)
            for (int j = 1; j < 2 * n; j+=2)
                map[i][j] = '*';*/把点标记成‘*’，输出map可以看得更直观
        for (int i = 0; i < m; i++)
        {
            cin >> hv >> x >> y;
            if (hv == 'H')map[2* x - 1][2 * y] = '1';//把‘1’改成‘-’可以在map上看得更直观
            else map[2 * y][2 * x - 1] = '1';
        }
        flag = 0;
        if (time != 1)printf("\n**********************************\n\n");
        printf("Problem #%d\n\n", time);
        for (int i = 1; i <= n; i++)
            if (find(i))flag = 1;
        if (!flag)printf("No completed squares can be found.\n");
    }
    return 0;
}