P1845 影像之结构化特征_NOI导刊2011提高(12)

    • 113通过
    • 569提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 NOI导刊 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在影像比对中,有一种方法是利用影像中的边缘(edge)资讯,计算每个边缘资讯中具有代表性的结构化特征,以作为比对两张影像是否相似的判断标准。Water-filling方法是从每个边缘图的一个端点开始,绕着相连的边缘点走并依序编号。若走到某一步时,遇到一个以上不同的连接点,则分成不同路径同时继续走,直到没有任何连接点为止。如果一个点和另一个点为上下左右相邻,就称为连接。 

    例如,在图1的影像中包含三个边缘图,每个边缘图由一些互相连接的边缘点构成。图中以黑色的方块代表边缘点,白色的方块代表背景。在Water-filling方法中,首先,从第一行(row)开始,由左至右,由上至下,先找到第一个黑点并编号为1。接着,找1的下一个尚未编号的连接点并编号为2。依此方法继续往下一个点前进依次编号。在编号6的点之后有两个尚未编号的连接点,此时,则分为两条路线,并同时编号为7继续往下走。当走到没有任何的相连点时,则结束现有边缘图的编号,并继续对影像中的其它边缘图编号。走完图1所有边缘图后所得到的编号如图2所示。所以,走完这三个边缘图所需要的步数分别为12、7及3;所以,12、7及3可以作为代表此张影像的结构化特征。请注意:位于斜对角上的两点不能算做连接,如:

    请写一个程序计算每个影像中,以Water-filling方法走完其中所有的边缘图后,将每个边缘图需走的步数依走访的顺序列出。

    输入输出格式

    输入格式:

    输入文件包含一个正方形的影像。每组影像以图的宽度n开头(l≤n≤1000)。接下来的n行代表影像的内容:0表示背景的白点,1表示黑色的边缘点。 

    输出格式:

    对每一个输入的影像,以Water-filling方法走完所有的边缘图后,先印出此张影像中共有几个边缘图。接着,将每个边缘图需走的步数按升序列出。

    输入输出样例

    输入样例#1: 复制
    10 
    0000000000 
    0011110000 
    0000010000 
    0011111000 
    0010110100 
    0010010110 
    0011110010 
    0100010010 
    0100000110 
    0100000000 
    输出样例#1: 复制
    3 
    3 
    7 
    12
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。