UVA201

题目

题目大概的意思就是给你一个二维的正方形矩阵.

第一行会给出这个正方形矩阵的每一行由n个点组成(2<=n <= 9), 第二行会给出要输入的边的数据.每一行以一个字母H或者V开头, 表示这是一个横向的边或者是一个竖向的边.其中H i j, 表示这条边是(i,j)-(i, j +1).V i j 表示的是(j, i)-(j + 1, i).就是这里, 如果你不注意看题, 可能会以为V i j也是(i, j)-(i + 1, j).然后要求你求能构成变成为len( 1=<len <= 8)的所有正方形, 并按照个数从小到大输出.

题目是我根据看完后自己翻译加上一些逻辑的推理整理的, 等价于原题, 不过其中就包含了思考的过程, 所以你最好自己看原题.

分析

思路:

题目的思路也很直接, 我用sides数组表示sides(i, j)为节点i到j有边board(i, j)表示这个(i, j)点属于某一条边.通过实现squareCount(board, len, size)函数来计算, 该矩阵中为len长度的正方形有几个.

数据预处理:

首先对于每一条边是这样处理的, 如果是H. 则将board(i, j)标记为1, 并判断 j + 1有没有越界, 没有的话, board(i, j + 1)也标记为1, 然后分别将这两个二维坐标映射到唯一的一个整数, 即 (i - 1) * size + j, 分别计算出其节点整数值为a,b 然后将sides(a, b) = sides(b, a)标记为1, 表示这是一条无向的边.

实现主要函数:

squareCount(), 该函数的实现也很直接, 我们就枚举左上角为(i ,j )的正方形, 看其存不存在.

API

快排: qsort(array, arrayNum, elementSize, cmpFunc).前三个参数比较容易理解, 后面这个cmpFunc函数指针比较肯定, 我们一般需要自己实现这个函数, 来让自己的对象支持排序.并且这个cmpFunc函数的参数类型要完全和函数指针定义的类型完全一至

//
// Created by sixleaves on 16/11/25.
//

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 12
#define MAXSIDES 100

typedef struct {
    int size;
    int count;

}result;

int sides[MAXSIDES][MAXSIDES];
int boards[MAXN][MAXN];
char readchar() {
    char ch;
    for (;;) {
        ch = getchar();
        if ('\n' != ch && '\r' != ch) return ch;
    }
}

// 判断从(r, c)点开始有没有长度为len的正方形
int isSquare(int r, int c, int len, int maxR) {


    int isExsit = true;
    // V
    int startX = r, startY = c;
    for (int endX = r + 1; endX <= r + len; endX++) {

        int endY = startY;
        if (endX <= maxR && boards[endX][endY]) {
            int nodeS = (startX - 1) * maxR + startY;
            int nodeE = (endX - 1) * maxR + endY;
            if (!sides[nodeS][nodeE]) {
                isExsit = false;
                break;
            }else {
                startX = endX;
            }
        }else {
            isExsit = false;
            break;
        }
    }

    // H
    startX = r, startY = c;
    for (int endY = c + 1; endY <= c + len; endY++) {
        int endX = startX;
        if (endY<= maxR && boards[endX][endY]) {
            int nodeS = (startX - 1) * maxR + startY;
            int nodeE = (endX - 1) * maxR + endY;
            if (!sides[nodeS][nodeE]) {
                isExsit = false;
                break;
            }else {
                startY = endY;
            }
        }else {
            isExsit = false;
            break;
        }
    }


    r = r + len;
    c = c + len;
    if (r <= maxR && c <= maxR && boards[r][c]) {
        // V
        startX = r, startY = c;
        for (int endX = r - 1; r - len >=1 && endX >=  r - len; endX--) {
            int endY = startY;
            if (endX >= 1 && boards[endX][endY]) {
                int nodeS = (startX - 1) * maxR + startY;
                int nodeE = (endX - 1) * maxR + endY;
                if (!sides[nodeS][nodeE]) {
                    isExsit = false;
                    break;
                }else {
                    startX = endX;
                }
            }else {
                isExsit = false;
                break;
            }
        }

        // H
        startX = r, startY = c;
        for (int endY = c -1; c- len >= 1 && endY >= c - len; endY--) {
            int endX = startX;
            if (endY >= 1 && boards[endX][endY]) {
                int nodeS = (startX - 1) * maxR + startY;
                int nodeE = (endX - 1) * maxR + endY;
                if (!sides[nodeS][nodeE]) {
                    isExsit = false;
                    break;
                }else {
                    startY = endY;
                }
            }else {
                isExsit = false;
                break;
            }
        }
    }else {
        isExsit = false;
    }
    return isExsit;
}

int squareCount(int board[][MAXN], int maxR, int len) {
    int count = 0;
    for (int r = 1; r <= maxR; r++) {

        for (int c = 1; c <= maxR; c++) {
            // 以r,c为左上角的正方形存在
            if (board[r][c] && isSquare(r, c, len, maxR)) {
                count++;
            }
        }

    }
    return count;
}

int comp(const void *cmp1, const void *cmp2) {
    return ((result *)cmp1)->size - ((result *)cmp2)->size;
}

int main() {

    int n;
    int k = 0;
    int isfirst = true;
    while (scanf("%d", &n) != EOF) {
        if (!isfirst) printf("\n**********************************\n\n");
        isfirst = false;

        printf("Problem #%d\n\n", ++k);
        memset(sides, 0, sizeof(sides));
        memset(boards, 0, sizeof(boards));
        int s;
        scanf("%d", &s);

        for (int i = 1; i <=s; i++) {
            char ch = readchar();
            int x, y;
            scanf("%d%d", &x, &y);
            if (ch == 'H') {
                int nodeR = (x - 1) * n + y;
                int nodeC = (x - 1) * n + y + 1;
                boards[x][y] = 1;
                if (y + 1 <= n) {
                    boards[x][y + 1] = 1;
                    sides[nodeR][nodeC] = sides[nodeC][nodeR] = 1;
                }

            }else {
                int nodeR = (y- 1) * n + x;
                int nodeC = y * n + x;
                boards[y][x] = 1;
                if (y + 1 <= n) {
                    boards[y + 1][x] = 1;
                    sides[nodeR][nodeC] = sides[nodeC][nodeR] = 1;
                }
            }
        }


        int sum = 0;
        result ans[9];
        for (int i = 0; i < 9; i++) {
            ans[i].count = 100000;
            ans[i].size = 100000;
        }
        int i = 0;
        for (int len = 1; len <= 8; len++) {
            int cnt = squareCount(boards, n, len);
            sum +=cnt;
            if (cnt) {
                ans[i].size = len;
                ans[i].count = cnt;
                i++;
            }
        }

        // 从小到达排序
        qsort(ans, 9, sizeof(result), &comp);

        if (!sum) printf("No completed squares can be found.\n");
        else {
            for (int k = 0; k < i; k++) {
                printf("%d square (s) of size %d\n", ans[k].count, ans[k].size);
            }
        }
    }
    return 0;
}