检测“位图中”的形状

2024-04-13

所以,在为下一场 ieextreme 比赛做准备时,我遇到了一些过去的问题。我发现一个真正困扰我的问题,因为我不知道该怎么做。我可能可以使用一些 300 行的暴力代码来实现它,但我我认为这不是在这样的比赛中应该做的事情,所以我需要你的帮助!

检测位图中的形状

问题陈述:在图像分析中,通常分析位图并观察其中存在的形状。对于此问题,设计一种算法来检测给定位图中的形状。地图中出现的形状应来自正方形、矩形、三角形和平行四边形集合。

在位图中,每个像素都表示为一个位,1 - 代表黑色,0 - 代表白色。参与者需要检测出黑色轮廓的形状。输入 第一行将包含位图的大小(以像素为单位),表示为(行,列)。

例如。 6,8 这意味着 6 行 8 列的位图。下一行将包含一系列从 0 到 255 的十进制数字,并用空格分隔。位图中的每个数字代表 8 个二进制位的集合。 IE。 55代表二进制模式00110111。

注意:位图中可以有多个形状,并且形状不得相交。然而,形状可以相互嵌套而没有任何交叉。

输出 位图中出现的形状按其名称的升序排列,并用逗号和空格分隔。例如。长方形、正方形、三角形

注意:输出末尾没有换行或空格 如果任何形状重复,则输出应包含与位图中一样多的重复。 IE。如果有 2 个正方形和 1 个三角形,则输出应为 Square、Square、Triangle

示例集 1

Input:

6 8

0 126 66 66 126 0

输出:矩形

示例集 2

Input:

6 16

0 0 120 120 72 144 73 32 123 192 0 0

输出:平行四边形、正方形

我编写了这段代码,以便我可以可视化位图并有 2 个列表(行和列中的位图)...

rows,cols=(int(i) for i in raw_input().split())
nums=[int(n) for n in raw_input().split()]
mr=[]
for i in range(0,len(nums),cols/8):
    row=''
    for j in range(i,i+cols/8):
        b=bin(nums[j])[2:]
        b='0'*(8-len(b))+b
        row+=b
    mr.append(row)
mc=[''.join([mr[i][j] for i in range(rows)]) for j in range(cols)]

谢谢您的时间...请用Python、C++或Ruby回答,因为这些是我能理解的语言,甚至是算法上的...


我的方法是这样的:

  1. 找到第一个黑色像素(最左到最上,或最上到最左)。
  2. 向右和向下追踪黑色路径(也就是说,循环直到遇到白色像素)。
  3. 3 cases:

    • 路径具有相同的长度:正方形或三角形。检查左下像素右侧的像素来决定(黑色:正方形,白色:三角形)。
    • 路径具有不同的长度:矩形或三角形(?或者它们应该始终为 45 度?)。检查左下像素右侧的像素来决定(黑色:矩形,白色:三角形)。
    • 其中一条路径不存在:三角形或平行四边形。假设向下的路径did存在:检查左下像素右侧的像素来决定(黑色:三角形,白色:平行四边形)。
  4. 删除形状并重复。

您仅检查每个像素固定次数(不太确定该常数),因此这应该在时间上与像素数量呈线性关系。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

检测“位图中”的形状 的相关文章

  • 在 n log n 时间内打乱链表的算法

    我正在尝试使用分治算法对链表进行洗牌 该算法以线性 n log n 时间和对数 log n 额外空间随机洗牌链表 我知道我可以进行类似于在简单的值数组中使用的 Knuth 洗牌 但我不确定如何通过分而治之来做到这一点 我的意思是 我实际上在
  • 如何求能被7整除的数字个数?

    给定一个整数N 如何有效地找到范围内能被 7 整除的数字的个数 其逆序也能被 7 整除 0 10 N 1 Example For N 2 回答 4 0 7 70 77 0到99之间所有能被7整除的数字 它们的倒数也能被7整除 我的方法 简单
  • 如何在文本文件中找到最长的 N 行并将其打印到标准输出?

    第一行包含数字 N 的值 后跟多行 我可以按照n 2算法的顺序解决它 有人可以建议一个更好的吗 您可以使用最小堆并在 O n log N 中完成 heap new Min Heap N foreach line in text if len
  • 3 维装箱算法

    我面临着 3 维装箱问题 目前正在进行一些初步研究 了解哪些算法 启发式方法目前能产生最佳结果 由于问题是 NP 难问题 我不希望在每种情况下都能找到最佳解决方案 但我想知道 1 最好的精确求解器是什么 分支定界 我期望使用合理的计算资源可
  • 通过 DFS 查找图中的强连通分量

    我正在阅读有关 BFS 和 DFS 的图算法 当我分析通过DFS在图中查找强连通分量的算法时 我想到了一个疑问 为了找到强连通分量 书 Coremen 做了什么 首先它在图上运行 DFS 以获得顶点的完成时间 然后再次以完成时间的降序在图的
  • C++ STL 下一个排列与组合

    我知道我可以使用std next permutation在包含元素的某些容器上 1 2 3 这将生成该序列的 6 种排列 我想做的是给定一些设置 1 2 3 4 5 6 生成大小为 3 的所有可能的排列 因此对于这个例子 4 3 2 将是由
  • 不均匀圆盘的最佳覆盖

    What kind of algorithm can I use to search for an optimal minimum area covering of a limited region of the XY plane with
  • 产生独特的价值

    我想创建一个C程序生成 0 到 999999 之间的数字 请记住生成的数字不应包含任何重复的数字 例如 123 是一个可接受的值 但不是 121 as the 1 被重复 我已经找到了其他程序代码来检查整数是否有重复的数字 检查整数是否有重
  • Java 中的递归回溯解决填字游戏

    我需要在给定初始网格和单词的情况下解决填字游戏 单词可以多次使用或根本不使用 初始网格如下所示 这是一个单词列表示例 pain nice pal id 任务是填充占位符 水平或垂直长度 gt 1 像那样 p pain pal id i c
  • 在等式约束的情况下求解线性规划

    我问了一个问题 可以在这里找到 计算最优组合 https stackoverflow com questions 17232596 computing the optimal combination 并有人建议线性规划 我查阅了线性规划和单
  • 是否有一种仅使用极坐标来查找附近点的算法?

    假设我有一个点向量作为极坐标 假设其中一个点充当探针 我想找到一定距离内的所有其他点 是否有一种算法可以在不将它们转换为笛卡尔形式的情况下执行此操作 您正在寻找极坐标的距离 你可以在这里找到公式link http math ucsd edu
  • Perl 初学者:如何查找/替换文件中的 ASCII 字符?

    我对 Perl 完全陌生 我认为这将是解决我的简单任务的最佳语言 我需要将二进制文件转换为可读的文件 并且需要查找和替换字符串 例如 x00 x39 into x09 选项卡 或类似的东西 从 bash 开始 我从以下内容开始 效果很好 p
  • 二分图中最小顶点覆盖算法

    我正在尝试找出一种算法来查找二分图的最小顶点覆盖 我正在考虑一个解决方案 将问题减少到二分图中的最大匹配 众所周知 可以使用从 bip 创建的网络中的最大流量来找到它 图形 最大匹配 M 应确定最小匹配 顶点覆盖 C 但我无法处理选择顶点来
  • 将自行车分配给人员 - 第一优先级(距离最近的人最近的自行车)

    将网格传递给某个位置有自行车和人员的函数 c A a b D d B C Output 像这样的东西 A 1 B 3 C 8 D 1 其中 A 是人 1 是到达自行车所需的步数 标准 距离自行车最近的人 优先获得自行车 单辆自行车不能分配给
  • 简化债务加权有向图的算法

    我一直在使用我编写的一个小Python脚本来管理室友之间的债务 它有效 但缺少一些功能 其中之一是简化不必要的复杂债务结构 例如 如果下面的加权有向图代表一些人 箭头代表他们之间的债务 爱丽丝欠鲍勃 20 美元 查理欠 5 美元 鲍勃欠查理
  • 有没有快速的矩阵求幂方法?

    Is there any faster method of matrix exponentiation to calculate Mn where M is a matrix and n is an integer than the sim
  • 证明:为什么 java.lang.String.hashCode() 的实现与其文档相符?

    JDK 文档为java lang String hashCode http java sun com javase 6 docs api java lang String html hashCode famously https stack
  • Java Paint 组件转换为位图

    我需要在位图中绘制组件及其所有子组件的内容 如果我想绘制整个组件 以下代码可以完美运行 public void printComponent Component c String format String filename throws
  • OT 和 CRDT 之间的区别

    有人可以简单地向我解释一下操作转换和 CRDT 之间的主要区别吗 据我了解 两者都是允许数据在分布式系统的不同节点上无冲突地收敛的算法 在哪种用例中您会使用哪种算法 据我了解 OT主要用于文本 而CRDT更通用 可以处理更高级的结构 对吧
  • 以有效的方式找到最近点

    我在 2d 平面上有一个点 例如 x0 y0 和一组 n 点 x1 y1 xn yn 我想在 a 中找到距离 x0 y0 最近的点比尝试所有要点要好得多 有什么解决办法吗 我还应该说我的观点是这样排序的 bool less point a

随机推荐