首页 > 代码库 > uva 201 - Squares(自己的方法,同学有更好一点点的方法)

uva 201 - Squares(自己的方法,同学有更好一点点的方法)

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int h[20][20];
int v[20][20];
int size_[20];
int n,m;
int flag;

void judge(int x,int y)//这是关键部分的代码,用来判读那是否能构成square;
{
    int a1=n-x;
    int a2=n-y;
    int aa=min(a1,a2);
    for(int i=0; i<aa; i++)
    {
        if(h[x][y+i]&&v[x+i][y])
        {
            int j;
            for(j=0; j<=i; j++)
            {
                if(!(h[x+i+1][y+j])||!(v[x+j][y+i+1]))
                {
                    break;
                }
                if(j==i)
                {
                    flag=1;
                    size_[i]++;
                }
            }
        }
        else
            break;
    }
}

int main()
{
    int kase=0;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%d",&m);
        kase++;
        flag=0;
        memset(size_,0,sizeof(size_));
        memset(h,0,sizeof(h));
        memset(v,0,sizeof(v));
        int a1,a2;
        string s;
        for(int i=0; i<m; i++)
        {
            cin>>s>>a1>>a2;
            if(s=="H")
            {
                h[a1][a2]=1;
            }
            if(s=="V")
            {
                v[a2][a1]=1;
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(h[i][j]&&v[i][j])
                {
                    judge(i,j);
                }
            }
        }
        if(kase!=1)
        printf("\n**********************************\n");
            printf("Problem #%d\n\n",kase);
        if(flag==1)
        {
            for(int i=0; i<20; i++)
            {
                if(size_[i]!=0)
                {
                    printf("%d square (s) of size %d\n",size_[i],i+1);
                }
            }
        }
        else
            printf("No completed squares can be found.\n");
    }
    return 0;
}