uva 201の正方形の数
2059 ワード
http://acm.bnu.edu.cn/v3/contest_show.php?cid=5772落problem/B
点からなるグリッドを一つあげて、隣接点を結ぶ操作(横、縦)をあげて、中の正方形を統計して、小さい時から大出力します。
水は題を書いて、順次列挙します。各点が左上の角の時に正方形を構成することができるかどうかを判断します。
点からなるグリッドを一つあげて、隣接点を結ぶ操作(横、縦)をあげて、中の正方形を統計して、小さい時から大出力します。
水は題を書いて、順次列挙します。各点が左上の角の時に正方形を構成することができるかどうかを判断します。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
#define eps 1e-9
const double pi = acos(-1.0);
typedef long long LL;
const int inf = 1000000000;
const int maxn = 15;
int h[maxn][maxn],v[maxn][maxn],n,m;
int main()
{
int _ = 0;
while(~RD2(n,m)){
int x,y;
char typ[2];
clr0(h),clr0(v);
while(m--){
scanf("%s",typ);
RD2(x,y);
if(typ[0] == 'H')
h[x][y] = 1;
else
v[y][x] = 1;
}
if(_++) puts("
**********************************
");
printf("Problem #%d
",_);
int sum = 0;
for(int l = 1;l <= n;++l){
int cnt = 0;
for(int i = 1;i + l <= n;++i)
for(int j = 1;j + l <= n;++j){
int flag = 1;
for(int hh = j;hh < j + l;++hh)
if(!h[i][hh] || !h[i+l][hh])
flag = 0;
for(int vv = i;vv < i + l;++vv)
if(!v[vv][j] || !v[vv][j+l])
flag = 0;
cnt += flag;
}
sum += cnt;
if(cnt)
printf("%d square (s) of size %d
",cnt,l);
}
if(!sum)
puts("No completed squares can be found.");
}
return 0;
}