UVA201 正方形 Squares

    • 64通过
    • 162提交
  • 题目来源 UVA 201
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题意翻译

    题目描述

    一个儿童棋盘游戏,包含了由点组成的正方形矩阵,由线段连接了一些相邻的点。游戏的一个环节是,要求玩家数出由这些线段所形成的特定大小的正方形有多少个。例如,按下图所示,有 3 个正方形,其中大小为 1 的有 2 个,大小为 2 的有 1 个。正方形的 “大小” 是指构成它的一条边的线段数。

    你的任务是编写程序,自动对全部可能的正方形计数。

    输入输出格式

    输入格式

    输入包含了多个游戏棋盘。每个棋盘包含了 n^2 个点的正方形矩阵 (其中 2 ≤ n ≤ 9),以及一些起连接作用的横向或纵向的线段。棋盘的的 n^2 个点和 m 条连接线段,格式如下:

    第 1 行:n,表示矩阵中单行或单列的点的数目
    第 2 行:m,表示连接线段的数目
    接下来的 m 行,每行是以下两种格式之一:
    (1) H i j 形式,表示第 i 行的横向线段,连接了第 j 列的点和它右边的第 j + 1 列的点;
    (2) V i j 形式,表示第 i 列的纵向线段,连接了第 j 行的点和它下方的第 j + 1 行的点。

    样例输入数据的第 1 组,对应于上面的图示棋盘。

    输出格式

    对于每组测试数据,输出 Problem #1, Problem #2 等标识,并输出棋盘上的各种大小的正方形数目,按正方形由小到大的顺序排列。如果不存在任何大小的正方形,则打印相应的提示消息。将各组测试数据以一行星号间隔,星号上下方各有一个空行。请参见示例的格式。

    ——translated by Core

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    Problem #1
    2 square (s) of size 1
    1 square (s) of size 2
    **********************************
    Problem #2
    No completed squares can be found.
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。