博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[UVa 201]Squares 正方形,ACM/ICPC World Finals 1990
阅读量:6543 次
发布时间:2019-06-24

本文共 3024 字,大约阅读时间需要 10 分钟。

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

The input file represents a series of game boards. Each board consists of a description of a square array

of n
2 dots (where 2 ≤ n ≤ 9) and some interconnecting horizontal and vertical lines. A record for a
single board with n
2 dots and m interconnecting lines is formatted as follows:
Line 1: n the number of dots in a single row or column of the array
Line 2: m the number of interconnecting lines
Each of the next m lines are of one of two types:
H i j indicates a horizontal line in row i which connects
the dot in column j to the one to its right in column j + 1
or
V i j indicates a vertical line in column i which connects
the dot in row j to the one below in row j + 1
Information for each line begins in column 1. The end of input is indicated by end-of-file. The first
record of the sample input below represents the board of the square above.

Output

For each record, label the corresponding output with ‘Problem #1’, ‘Problem #2’, and so forth. Output

for a record consists of the number of squares of each size on the board, from the smallest to the largest.
lf no squares of any size exist, your program should print an appropriate message indicating so. Separate
output for successive input records by a line of asterisks between two blank lines, like in the sample
below.

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
‘**********************************’(两个单引号是我加的,因为我用的是MarkDown编辑器。。。)
Problem #2
No completed squares can be found.

题意:有n行n列(2<=n<=9)的点,还有m条线段连接其中的一些点。统计这些线段练成了多少个正方形。

解题思路:将读进来的要添加的边分别用两个bool数组存,添加后就将相应的位置赋值成true,然后枚举正方形的边长和左上角顶点的位置,统计答案。

代码

#include
using namespace std;int n,m,cnt;int ans[20];bool a[20][20],b[20][20];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int main(){ while(scanf("%d%d\n",&n,&m)!=EOF){ cnt++; if(cnt!=1)puts("\n**********************************\n"); memset(ans,0,sizeof(ans)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1;i<=m;i++){ char ch=getchar();int x=read(),y=read(); if(ch=='H')a[x][y]=true; else b[y][x]=true;//这个lrj的紫书上的描述应该是b[x][y],但是原题上的描述是b[y][x] } for(int s=1;s

转载于:https://www.cnblogs.com/Luvwgyx/p/8434854.html

你可能感兴趣的文章
双击防止网页放大缩小HTML5
查看>>
C#的一些学习方法
查看>>
U3D Invoke() IsInvoking CancelInvoke方法的调用
查看>>
Javascript 如何生成Less和Js的Source map
查看>>
中间有文字的分割线效果
查看>>
<悟道一位IT高管20年的职场心经>笔记
查看>>
volatile和synchronized的区别
查看>>
10.30T2 二分+前缀和(后缀和)
查看>>
vuex视频教程
查看>>
Java 线程 — ThreadLocal
查看>>
安居客爬虫(selenium实现)
查看>>
-----二叉树的遍历-------
查看>>
ACM北大暑期课培训第一天
查看>>
F. Multicolored Markers(数学思维)
查看>>
Centos7安装搜狗输入法
查看>>
nodjs html 转 pdf
查看>>
Python字典
查看>>
ofstream 的中文目录问题
查看>>
Android存储方式之SQLite的使用
查看>>
洛谷P1287 盒子与球 数学
查看>>