同和新媒体矩阵官网同和视频矩阵同和素材矩阵
同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21092_HistologyAssistan

2022-5-16 18:18| 发布者: Hocassian| 查看: 39| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504828537600-Problem List-采集的数据-后羿采集器.html

Pro.ID

21092

Title

Histology Assistant

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21092

AC

0

Submit

0

Ratio

-

时间&空间限制

  • Time Limit: 1500/500 MS (Java/Others)     Memory Limit: 131072/65536 K (Java/Others)

    • 描述

    An application to assist in the analysis of tissue samples is to work as follows. A digital microphotograph of a stained tissue sample is scanned to identify stained pixels. For each region of stained pixels, an outline of the region is obtained. The outline is then analyzed for shape indicators of disease and the outlines (color-coded for possible disease) are overlaid on the microphotograph as it is displayed to the pathologist.

    This problem is to write a program, which processes a bitmap of stained and unstained pixels, finds regions of stained pixels and, for each region, outputs the outline of the region. Regions with fewer stained pixels than a minimum size are ignored. Only the outer boundary is computed (interior holes are ignored).

    A pixel is adjacent to another pixel if the second pixel is directly above, directly below, directly left or directly right of the first pixel. Two stained pixels are connected if there is a sequence of stained pixels starting with one of the pixels and ending with the other for which each pixel in the sequence is adjacent to the next. A region of stained pixels is a set of stained pixels, all of which are connected to a single stained pixel. A stained pixel is a boundary pixel of its region if at least one of the pixels adjacent to it is not stained. (All pixels immediately outside the bitmap are considered unstained so that pixels on the edge of the bitmap are boundary pixels.) In the example below, there are 4 regions (stained pixels are `X', unstained are `.').

                       ........................................

                       .XX.....................................

                       ..X.................XXX......XXX........

                       .....................XXX....XXX.........

                       .......XXX............XXX..XXX..........

                       .....XXXXXXX...........XXXXXX...........

                       ....XXXXXXXXX...........XXXX............

                       ...XXXX...XXXX...........XX.............

                       ..XXX.......XXX.........................

                       ..XXX.......XXX........XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       ..XXX.......XXX...........X.............

                       ..XXX.......XXX...........X.............

                       ...XXXX...XXXX.........XXXXXXX..........

                       ....XXXXXXXXX..........XXXXXXX..........

                       .....XXXXXXX...........XXXXXXX..........

                       .......XXX.............XXXXXXX..........

                       ........................................

    Outlines are to be specified as the left most point of the top most line of the region, a count of boundary pixels and a sequence of moves from one boundary pixel to the next clockwise using the codes (up = A, up right = B, etc.):

                 H A B

                 G   C

                 F E D

    Rows are numbered from top to bottom beginning with 1. Columns are numbered from left to right beginning with 1. For example the outline of the `v' shaped region above would be: 

    3 21 22

    CCDDDCBBBCCFFFFFGHHHHH

    输入

    Input is a sequence of problem instances. Each problem instance begins with a line containing 3 decimal numbers: row-count, column-count and minimum-number-of-pixels. This line is followed by row-count lines of column-count characters. Each character is either a period (.) for an unstained pixel or an upper-case `X' for a stained pixel. The input ends when the row-count is 0. Row-count will be at most 47, column-count will be at most 63 and minimum- number-of-pixels will be at least 2.

    输出

    Description

    An application to assist in the analysis of tissue samples is to work as follows. A digital microphotograph of a stained tissue sample is scanned to identify stained pixels. For each region of stained pixels, an outline of the region is obtained. The outline is then analyzed for shape indicators of disease and the outlines (color-coded for possible disease) are overlaid on the microphotograph as it is displayed to the pathologist.

    This problem is to write a program, which processes a bitmap of stained and unstained pixels, finds regions of stained pixels and, for each region, outputs the outline of the region. Regions with fewer stained pixels than a minimum size are ignored. Only the outer boundary is computed (interior holes are ignored).

    A pixel is adjacent to another pixel if the second pixel is directly above, directly below, directly left or directly right of the first pixel. Two stained pixels are connected if there is a sequence of stained pixels starting with one of the pixels and ending with the other for which each pixel in the sequence is adjacent to the next. A region of stained pixels is a set of stained pixels, all of which are connected to a single stained pixel. A stained pixel is a boundary pixel of its region if at least one of the pixels adjacent to it is not stained. (All pixels immediately outside the bitmap are considered unstained so that pixels on the edge of the bitmap are boundary pixels.) In the example below, there are 4 regions (stained pixels are `X', unstained are `.').

                       ........................................

                       .XX.....................................

                       ..X.................XXX......XXX........

                       .....................XXX....XXX.........

                       .......XXX............XXX..XXX..........

                       .....XXXXXXX...........XXXXXX...........

                       ....XXXXXXXXX...........XXXX............

                       ...XXXX...XXXX...........XX.............

                       ..XXX.......XXX.........................

                       ..XXX.......XXX........XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       .XXX.........XXX.......XXXXXXX..........

                       ..XXX.......XXX...........X.............

                       ..XXX.......XXX...........X.............

                       ...XXXX...XXXX.........XXXXXXX..........

                       ....XXXXXXXXX..........XXXXXXX..........

                       .....XXXXXXX...........XXXXXXX..........

                       .......XXX.............XXXXXXX..........

                       ........................................

    Outlines are to be specified as the left most point of the top most line of the region, a count of boundary pixels and a sequence of moves from one boundary pixel to the next clockwise using the codes (up = A, up right = B, etc.):

                 H A B

                 G   C

                 F E D

    Rows are numbered from top to bottom beginning with 1. Columns are numbered from left to right beginning with 1. For example the outline of the `v' shaped region above would be: 

    3 21 22

    CCDDDCBBBCCFFFFFGHHHHH

    Input
    Input is a sequence of problem instances. Each problem instance begins with a line containing 3 decimal numbers: row-count, column-count and minimum-number-of-pixels. This line is followed by row-count lines of column-count characters. Each character is either a period (.) for an unstained pixel or an upper-case `X' for a stained pixel. The input ends when the row-count is 0. Row-count will be at most 47, column-count will be at most 63 and minimum- number-of-pixels will be at least 2.
    Output
    For each problem instance, the output begins with a line starting with a decimal integer giving the number of components of at least minimum-number-of-pixels stained pixels. This is followed by the description of the boundary of each component. The boundaries are to be listed in the order that a first pixel of the component appears while scanning across lines from left to right with line scanned from top to bottom. For each component, the output begins with a line giving the row number of the start pixel, the column number of the start pixel and the number of pixels in the boundary as decimal integers separated by a single space. This line is followed by lines of direction codes 'A' through 'H'. Each line shall have 40 characters except the last line.
    Sample Input
    20 40 4
........................................
.XX.....................................
..X.................XXX......XXX........
.....................XXX....XXX.........
.......XXX............XXX..XXX..........
.....XXXXXXX...........XXXXXX...........
....XXXXXXXXX...........XXXX............
...XXXX...XXXX...........XX.............
..XXX.......XXX.........................
..XXX.......XXX........XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
..XXX.......XXX...........X.............
..XXX.......XXX...........X.............
...XXXX...XXXX.........XXXXXXX..........
....XXXXXXXXX..........XXXXXXX..........
.....XXXXXXX...........XXXXXXX..........
.......XXX.............XXXXXXX..........
........................................
12 40 4
.X.X.X.X.X.X......XX...XXXXXXXXXXXXXXXX.
.XXX.XXX.XXX......XX..XXXXXXXXXXXXXXXXXX
.X...X...X........XX..XX.............XXX
.X.X.X.X.X.X......XX..XX...XXXXXXXX...XX
.XXX.XXX.XXX......XX..XX..XXXXXXXXXX..XX
.X...X...X........XX..XX..XX......XX..XX
.X.X.X.X.X.X......XX..XXX........XXX..XX
.XXX.XXX.XXX......XX..XXXXXXXXXXXXXX..XX
.X...X...X........XX...XXXXXXXXXXXX...XX
.X.X.X.X.X.X......XXX................XXX
.XXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXX
...................XXXXXXXXXXXXXXXXXXXX.
0 0 0
    Sample Output
    3
3 21 22
CCDDDCBBBCCFFFFFGHHHHH
5 8 36
CCDCDDDEDEEFEFFFGFGGHGHHHAHAABABBBCB
10 24 38
CCCCCCEEEGGFEDCCEEEGGGGGGAAACCBAHGGAAA
2
1 2 103
DBEGFEDBEGFEDBEGFEDBDBAAAAAAAAADBEGFEDBE
GFEDBEGFEDBDBAAAAAAAAADBEGFEDBEGFEDBEGFE
DBEGGGGGGGGGGAAAAAAAAAA
1 19 159
CEEEEEEEEDDCCCCCCCCCCCCCCCBBAAAAAHHGGGGG
GGGGGGGFEEEDDCCCCCCCBBHGGGGGFGABCCCCCCCD
EEEFGGGGGGGGGGGHAAAAAABCCCCCCCCCCCCCCCDE
EEEEEEEEFGGGGGGGGGGGGGGGGGGGHAAAAAAAAAA
    Source
    Greater New York 2004

    样例输入

    20 40 4
........................................
.XX.....................................
..X.................XXX......XXX........
.....................XXX....XXX.........
.......XXX............XXX..XXX..........
.....XXXXXXX...........XXXXXX...........
....XXXXXXXXX...........XXXX............
...XXXX...XXXX...........XX.............
..XXX.......XXX.........................
..XXX.......XXX........XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
.XXX.........XXX.......XXXXXXX..........
..XXX.......XXX...........X.............
..XXX.......XXX...........X.............
...XXXX...XXXX.........XXXXXXX..........
....XXXXXXXXX..........XXXXXXX..........
.....XXXXXXX...........XXXXXXX..........
.......XXX.............XXXXXXX..........
........................................
12 40 4
.X.X.X.X.X.X......XX...XXXXXXXXXXXXXXXX.
.XXX.XXX.XXX......XX..XXXXXXXXXXXXXXXXXX
.X...X...X........XX..XX.............XXX
.X.X.X.X.X.X......XX..XX...XXXXXXXX...XX
.XXX.XXX.XXX......XX..XX..XXXXXXXXXX..XX
.X...X...X........XX..XX..XX......XX..XX
.X.X.X.X.X.X......XX..XXX........XXX..XX
.XXX.XXX.XXX......XX..XXXXXXXXXXXXXX..XX
.X...X...X........XX...XXXXXXXXXXXX...XX
.X.X.X.X.X.X......XXX................XXX
.XXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXX
...................XXXXXXXXXXXXXXXXXXXX.
0 0 0

    样例输出

    3
3 21 22
CCDDDCBBBCCFFFFFGHHHHH
5 8 36
CCDCDDDEDEEFEFFFGFGGHGHHHAHAABABBBCB
10 24 38
CCCCCCEEEGGFEDCCEEEGGGGGGAAACCBAHGGAAA
2
1 2 103
DBEGFEDBEGFEDBEGFEDBDBAAAAAAAAADBEGFEDBE
GFEDBEGFEDBDBAAAAAAAAADBEGFEDBEGFEDBEGFE
DBEGGGGGGGGGGAAAAAAAAAA
1 19 159
CEEEEEEEEDDCCCCCCCCCCCCCCCBBAAAAAHHGGGGG
GGGGGGGFEEEDDCCCCCCCBBHGGGGGFGABCCCCCCCD
EEEFGGGGGGGGGGGHAAAAAABCCCCCCCCCCCCCCCDE
EEEEEEEEFGGGGGGGGGGGGGGGGGGGHAAAAAAAAAA

    作者


    路过
    雷人
    握手
    鲜花
    鸡蛋
    收藏 邀请

    最新评论

    相关分类

    QQ|Archiver|手机版|小黑屋|同和创作矩阵 ( 粤ICP备20019636号-1 )

    GMT+8, 2024-9-21 17:59 , Processed in 0.014708 second(s), 14 queries .

    Powered by Discuz! X3.4 Licensed

    © 2001-2017 Comsenz Inc.

    返回顶部