肿瘤检测

GitHub跳转原题关系图返回列表

统计灰度不超过 50 的肿瘤格，并以边界或四邻非肿瘤条件判断周长。

OJ: noi_openjudge

题目 ID: ch0108-19

难度:普及-

标签:矩阵模拟python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. Python代码
  7. C++代码
    1. 复杂度
    2. 总结

题意

灰度不超过 5050 的格属于肿瘤，求肿瘤面积和边界格数量。

思路

扫描每个肿瘤格累加面积。它位于图像边缘，或任一上下左右合法邻居不是肿瘤时，便是边界格，累加周长。

代码

cpp
#include <cstdio>

int n,m;
int a[200][200];
int cnt=0;
int fx[4][2] = { 0,-1, -1,0, 1,0, 0,1 };

void init(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
}

bool is_cancer(int x,int y){
    if( a[x][y] <=50)
        return 1;
    return 0;
}

bool in_map(int x,int y){
    if( x >=1 && x <= n && y >=1 && y <=n)
        return 1;
    return 0;
}

bool is_cancer_bound(int x,int y){
    if( is_cancer(x,y)){
        int i;
        for (i=0;i<4;i++){
            int nx = x + fx[i][0];
            int ny = y + fx[i][1];
            if( !is_cancer(nx,ny) || !in_map(nx, ny))
                return 1;
        }
        return 0;
    }
    return 0;
}
int main(){
    init();
    int i,j;
    int cnt_1 = 0;
    int cnt_2 = 0;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
                if( is_cancer(i, j))
                    cnt_1++;
                if( is_cancer_bound(i, j))
                    cnt_2++;
        }
    }
    printf("%d %d",cnt_1,cnt_2);
    return 0;
}

复杂度

总结

Python代码

python
size = int(input())
image = [list(map(int, input().split())) for _ in range(size)]
area = 0
perimeter = 0

for row in range(size):
    for column in range(size):
        if image[row][column] > 50:
            continue
        area += 1
        if row in (0, size - 1) or column in (0, size - 1) or any(image[row + dx][column + dy] > 50 for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) if 0 <= row + dx < size and 0 <= column + dy < size):
            perimeter += 1

print(area, perimeter)

C++代码

cpp
#include <cstdio>

int n,m;
int a[200][200];
int cnt=0;
int fx[4][2] = { 0,-1, -1,0, 1,0, 0,1 };

void init(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
}

bool is_cancer(int x,int y){
    if( a[x][y] <=50)
        return 1;
    return 0;
}

bool in_map(int x,int y){
    if( x >=1 && x <= n && y >=1 && y <=n)
        return 1;
    return 0;
}

bool is_cancer_bound(int x,int y){
    if( is_cancer(x,y)){
        int i;
        for (i=0;i<4;i++){
            int nx = x + fx[i][0];
            int ny = y + fx[i][1];
            if( !is_cancer(nx,ny) || !in_map(nx, ny))
                return 1;
        }
        return 0;
    }
    return 0;
}
int main(){
    init();
    int i,j;
    int cnt_1 = 0;
    int cnt_2 = 0;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
                if( is_cancer(i, j))
                    cnt_1++;
                if( is_cancer_bound(i, j))
                    cnt_2++;
        }
    }
    printf("%d %d",cnt_1,cnt_2);
    return 0;
}

复杂度

每格检查固定四邻居，时间复杂度为 O(n2)O(n^2)，矩阵空间为 O(n2)O(n^2)。

总结

区域边界判定的核心是检查相邻位置是否离开该区域或图像。