【UVA 201 --- Squares】模拟

【UVA 201 --- Squares】模拟

题目来源：点击进入【UVA 201 — Squares】

Description

A children’s board game consists of a square array of dots that contains lines connecting some of the
pairs of adjacent dots. One part of the game requires that the players count the number of squares of
certain sizes that are formed by these lines. For example, in the figure shown below, there are 3 squares
— 2 of size 1 and 1 of size 2. (The “size” of a square is the number of lines segments required to form
a side.)

Your problem is to write a program that automates the process of counting all the possible squares.

Input

Output

Sample Input

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1

Sample Output

Problem #1
2 square (s) of size 1
1 square (s) of size 2
**********************************
Problem #2
No completed squares can be found.

解题思路

模拟。直接用两个数组，记录横线和竖线。然后将所有长度都扫一遍即可。

AC代码：

#include <stdio.h>
#include <string.h>
const int MAXN = 10;
bool h[MAXN][MAXN],v[MAXN][MAXN];

int main()
{
    int n,m,x,y,cas=0;
    char ch;
    while(~scanf("%d%d",&n,&m))
    {
        memset(h,false,sizeof(h));
        memset(v,false,sizeof(v));
        while(m--)
        {
            scanf(" %c%d%d",&ch,&x,&y);
            if(ch=='H') h[x][y]=true;
            else v[y][x]=true;
        }
        if(cas++) printf("\n**********************************\n\n");
		printf("Problem #%d\n\n",cas);
        bool flag=false;
        for(int len=1;len<=n;len++)
        {
            int num=0,f=0;
            for(int i=1;i+len<=n;i++)
            {
                for(int j=1;j+len<=n;j++)
                {
                    f=1;
                    for(int k=j;k<j+len;k++)
                        if(!h[i][k] || !h[i+len][k]) f=0;
                    for(int k=i;k<i+len;k++)
                        if(!v[k][j] || !v[k][j+len]) f=0;
                    num+=f;
                }
            }
            if(num) printf("%d square (s) of size %d\n",num,len),flag=true;
        }
        if(!flag) printf("No completed squares can be found.\n");
    }
    return 0;
}