題目

輸入

分為三部分。
第一部分占一行，含一個(gè)整數(shù) n，代表 n*n 個(gè)點(diǎn)構(gòu)成的 n階 正方形。
第二部分占一行，含一個(gè)整數(shù) m，代表下面將輸入 m 行指令進(jìn)行連線。
第三部分占 m 行，每行含一個(gè)字符和兩數(shù)字，形如：

C i j

H i j 表示點(diǎn)（i，j）與點(diǎn)（i，j + 1）連線；
V i j 表示點(diǎn)（j，i）與點(diǎn)（j + 1，i）（這里要特別留意）連線；

處理

要求求出在該圖中有多少個(gè)正方形，且區(qū)分大?。╯ize 1~9）。

例子輸入輸出

分析

由于要儲(chǔ)存圖的這種特殊形式，所以想到用結(jié)構(gòu)體：含有四個(gè)指針0，1，2，3分別指向上方，右方，下方和左方。然后為了方便遍歷，所以用結(jié)構(gòu)體二維數(shù)組來(lái)儲(chǔ)存所有的點(diǎn)。
連線的時(shí)候就用指針指向?qū)?yīng)要連接的位置，沒(méi)有線的方向就用NULL。

遍歷要分兩大層：
第一大層是遍歷所有的可能滿足的起始點(diǎn)，這里用函數(shù)“包裝”，n 代表要查找的n階正方形（一條邊n個(gè)點(diǎn)）；max 代表該圖的實(shí)際大小，防止遍歷出界。不難發(fā)現(xiàn)，我們并不需要遍歷圖上所有點(diǎn)。因?yàn)槿绻鹗键c(diǎn)充當(dāng)小正方形的左上角，那起始點(diǎn)最多到max - n就可以了，再往后就會(huì)出界。
第二大層是遍歷從起始點(diǎn)出發(fā)的n階正方形（其實(shí)最多只有一個(gè)正方形）。用一個(gè)循環(huán)變量作方向（1，2，3，0順時(shí)針），另一個(gè)變量作邊長(zhǎng) n 個(gè)點(diǎn)（不是線）。如此循環(huán)如果是正方形必會(huì)返回到原點(diǎn)。但也要小心一動(dòng)不動(dòng)的也是在呆在原點(diǎn)，所以還要判斷這個(gè)點(diǎn)是否與右邊連線。
由此一來(lái)基本完成。

代碼

#define maxn 11
#include <stdio.h>
#include <string.h>

struct point{
    //0 ~ 3 代表從 向上 開(kāi)始順時(shí)針的四個(gè)方向
    struct point * con[4];
    point() { con[0] = con[1] = con[2] = con[3] = NULL;     }
    void clear() { con[0] = con[1] = con[2] = con[3] = NULL; }
} po[maxn][maxn];

void H(int r, int c) {
    po[r][c].con[1] = &po[r][c + 1];
    po[r][c+1].con[3] = &po[r][c];
}

void V(int c, int r) {
    po[r][c].con[2] = &po[r+1][c];
    po[r+1][c].con[0] = &po[r][c];
}

int check(int n, int max) {
    int num = 0;
    //遍歷所有要遍歷的點(diǎn)
    for (int i = 1; i <= max - n + 1; i++) for (int j = 1; j <= max - n + 1; j++) {
        struct point * p = &po[i][j];
        int flag = 1;
        //遍歷一個(gè)點(diǎn)是否連成一個(gè)完整的 n 階正方形，d 控制遍歷方向，k 控制邊長(zhǎng)
        for (int d = 1; flag; d = (d+1) % 4) for (int k = 1; k < n; k++) {
            if (p->con[d] == NULL) { flag = 0; break; }
            p = p->con[d];
            //d 為 0 既往上的時(shí)候退出方向的遍歷
            flag = d;
        }
        if (p == &po[i][j] && p->con[1] != NULL) ++num;
    }
    return num;
}

int main() {
#ifdef TEST
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // TEST

    int n, m, kase=0;
    while (scanf("%d", &n) != EOF && n) {
        scanf("%d", &m);
        //初始化點(diǎn)之間的連線
        for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) po[i][j].clear();
        //連線
        while (m--) {
            char cmd[5]; int i, j;
            scanf("%s%d%d", cmd, &i, &j);
            if (cmd[0] == 'H') H(i, j);
            else V(i, j);
        }
        //輸出
        if (kase++) printf("\n**********************************\n\n");
        printf("Problem #%d\n\n", kase);
        int ans[maxn], num, flag=0; 
        memset(ans, 0, sizeof(ans));
        for (int i = 2; i <= n; i++)
            if (num = check(i, n))   //i是點(diǎn)數(shù)，所以要 -1換算為邊數(shù)
                printf("%d square (s) of size %d\n", num, i-1), flag =1;
        if (!flag)printf("No completed squares can be found.\n");
    }
    return 0;
}