肿瘤面积

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

从矩形肿瘤边框左上角测量零边框宽高，计算去掉边框后的内部面积。

OJ: noi_openjudge

题目 ID: ch0108-18

难度:入门

标签:矩阵模拟数学python

日期: 2026-07-30 23:01

目录

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

题意

灰度图中肿瘤是零像素围成的矩形边框，求边框内部的像素数。

思路

最先扫描到的零是边框左上角。沿该行和该列数出边框宽高，内部尺寸分别减去两条边框，面积为 (height - 2) * (width - 2)。

代码

cpp
#include <cstdio>

int n;
int a[1005][1005];
int w,h;

int main(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            if( a[i][j] == 0){
                w = 1;
                h = 1;
                int pos = j;
                for(j=j+1;j<=n;j++){
                    if(a[i][j] == 0)
                        w++;
                    else
                        break;
                }
                for(j=i+1;j<=n;j++){
                    if( a[j][pos] == 0)
                        h++;
                    else
                        break;
                }

                int ans = w*h -( (w-2)*2+(h-2)*2+4);
                printf("%d\n",ans);

                return 0;
            }
        }
    }
    printf("0");
    return 0;
}

复杂度

总结

Python代码

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

for top in range(size):
    for left in range(size):
        if image[top][left] != 0:
            continue
        right = left
        while right < size and image[top][right] == 0:
            right += 1
        bottom = top
        while bottom < size and image[bottom][left] == 0:
            bottom += 1
        print(max(0, bottom - top - 2) * max(0, right - left - 2))
        raise SystemExit

print(0)

C++代码

cpp
#include <cstdio>

int n;
int a[1005][1005];
int w,h;

int main(){
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            if( a[i][j] == 0){
                w = 1;
                h = 1;
                int pos = j;
                for(j=j+1;j<=n;j++){
                    if(a[i][j] == 0)
                        w++;
                    else
                        break;
                }
                for(j=i+1;j<=n;j++){
                    if( a[j][pos] == 0)
                        h++;
                    else
                        break;
                }

                int ans = w*h -( (w-2)*2+(h-2)*2+4);
                printf("%d\n",ans);

                return 0;
            }
        }
    }
    printf("0");
    return 0;
}

复杂度

扫描图像并测量边框，时间复杂度为 O(n2)O(n^2)，矩阵空间为 O(n2)O(n^2)。

总结

已知规则矩形边框时，测量宽高即可直接得到内部面积。