UVa 201 - Squares

从上午开始想的,下午上完机又改了改,晚上过的,题目不难,属于一看就有思路的那种,一次Ac。用了两个数组统计H、V两个方向线段,然后加个函数判断。上机课做完实
验题之后,敲代码时学长跟我提到了循环太多,不过好在这道题数据量不大。提交之后看,运行时间确实比平时提交的题长不少,以后做题还是尽量要减少循环层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#define maxn 15
using namespace std;
int h[maxn][maxn],v[maxn][maxn];
int cnt[maxn];
char c;
int a,b,n,m;
int t=1,first=1;
void sr()
{
for(int i=0;i<m;i++)
{
cin>>c>>a>>b;
a--;
b--;
if(c=='H')
h[a][b]=1;
else if(c=='V')
v[b][a]=1;
}
}
void tj()
{
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1-i;j++)
{
for(int k=0;k<n-1-i;k++)
{
int p=1;
for(int l=0;l<i+1;l++)
{
if(!p)
break;
if(!h[j][k+l])
p=0;
if(!h[j+i+1][k+l])
p=0;
if(!v[j+l][k])
p=0;
if(!v[j+l][k+i+1])
p=0;
}
if(p)
cnt[i]++;
}
}
}
}
void sc()
{
int k=0;
if(first)
first=0;
else
{
cout<<endl;
cout<<"**********************************"<<endl;
cout<<endl;
}
cout<<"Problem #"<<t<<endl;
cout<<endl;
for(int i=0;i<n;i++)
{
if(cnt[i])
cout<<cnt[i]<<" square (s) of size "<<i+1<<endl;
else
k++;
}
if(n==k)
cout<<"No completed squares can be found."<<endl;
t++;
}
int main()
{
while(cin>>n)
{
cin>>m;
memset(cnt,0,sizeof(cnt));
memset(h,0,sizeof(h));
memset(v,0,sizeof(v));
sr();
tj();
sc();
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。