nbhkdz.com冰点文库

求图形面积


回专题模式 回学习阶段模式 【题目名称、来源】 求图形面积 mianji.pas(经典问题) 【问题描述】 具有不同颜色的 n 个矩形被叠放在一张白纸上,纸的尺寸可以看作为 a*b 的边长为 1 的格子组成。矩形也可以看作由 ai*bi 个边长为 1 的格子组成,摆放矩形时,必须使矩形的 边与纸的网格对齐, 并且每个矩形整个放在纸的边界之内。 因此可在纸上出现不同颜色的各 种不同

图形。 同一颜色的两个区域中如果至少有一个公共点, 则可以认为它们是同一图形的 一部分,否则认为是不同图形。要求,输入矩形摆放信息,输出共有多少个图形,每个图形 的面积是多少。 输入格式: a,b,n{ a,b 为整数 a<=30,b<=30,1<=n<=a*b div 2} {矩形长、宽都是整数,摆放时摆在白纸网格中的第几行、第几列,颜色 1<=c<=255} a0 b0 i0 j0 c0 a1 b1 i1 j1 c1 …… an bn in jn cn 输出格式: M{共有 m 个图形} s1 s2 ……sm{m 个图形的面积,按照从小到大的顺序输出} 【所属专题】 广度优先搜索 【适合学习阶段】 【解题思路】 问题分析: 本问题可以使用种子填充法 floodfill 来求解, 建立一个队列 Q。初始时,Q 中仅包含开始的那个“点” ,对于每个出队的元素,把它 周围需要扩散到的元素加入队列中。 为了避免重复访问, 需要记录每个元素是否已经被访问 过,即访问标志。这个算法的事件复杂度为 O(m),其中 m 是需要扩散到的元素总个数;附 加空间为 O(m),这是他访问标志所用空间。如果访问标志可以和原始数据共用一块内存, 则附加空间为 O[1] floodfill 是一种常用的与处理方法。当“连在一起很大一块东西可以一起处理”的时候, 可以作一次 floodfill,分离出一个个连在一起的块,然后再作处理。 存储结构: var zhi:array [1..30,1..30] of integer;{该方阵中 0 代表空,-1 代表已访问,其他代表颜色} que:array[1..2,1..900] of integer;{扩展队列} 程序框架: Function floodfill(i,j:integer):integer;{使用种子填充法找到一块相连的区域,返回区域面积} 主程序: For i:=1 to m do

For j:=1 to m do begin If zhi[I,j]>0 then begin begin count:=count+1; s[count]:=floodfill(I,j); end; End; 【测试数据】 【源程序】 program mianji; const direction:array[1..2,1..8] of integer={向八个方向走} ((-1,1, 0,0,-1,1,-1, 1), ( 0,0,-1,1,-1,1, 1,-1)); max=30;{方阵大小} var zhi:array[1..max,1..max] of integer; {白纸方阵其中每个单元为 0 没被占,-1 访问过,>0 颜色号} que:array[1..2,1..max*max]of integer;{队列} a,b,n:integer;{a,b 白纸行列数,n 颜色方块个数} s:array[1..(max*max)div 2] of integer;{矩形面积结果} ai,bi,ci,count,i0,j0:integer; {count 存储共有几个图形 ci 存储颜色} t,i,j,k:integer; function floodfill(i0,j0:integer):integer; {广度优先搜索从 i0,j0 点开始} var i1,j1,r:integer;{r 为规则号} closed,open,color:integer; begin {初始数据进队列} que[1,1]:=i0;que[2,1]:=j0;color:=zhi[i0,j0]; closed:=0;open:=1;zhi[i0,j0]:=-1; {开始搜索} while (closed<open)and(open<max*max) do begin closed:=closed+1; for r:=1 to 8 do begin {如果没有走出方阵,且队不满,且颜色一致} i1:=que[1,closed]+direction[1,r];j1:=que[2,closed]+direction[2,r]; if (i1>=1)and(i1<=a)and(j1>=1)and(j1<=b)and(zhi[i1,j1]>0) and(open<max*max)and(color=zhi[i1,j1])then begin {新节点入队} open:=open+1; que[1,open]:=i1; que[2,open]:=j1;

zhi[i1,j1]:=-1;{作标志} end; end; end; floodfill:=open;{返回总块数} end; begin fillchar(zhi,sizeof(zhi),0); assign(input,'mianji.in'); reset(input); readln(a,b,n); {读取方阵信息} for k:=1 to n do begin readln(ai,bi,i0,j0,ci); for i:=i0 to i0+ai-1 do for j:=j0 to j0+bi-1 do zhi[i,j]:=ci; end; close(input); {枚举所有可能 floodfill 的块} count:=0; for i:=1 to a do for j:=1 to b do begin if zhi[i,j]>0 then begin count:=count+1; s[count]:=floodfill(i,j); end; end; {冒泡排序} for i:=count downto 2 do for j:=1 to i-1 do begin if s[j]>s[j+1] then begin t:=s[j]; s[j]:=s[j+1]; s[j+1]:=t; end; end; assign(output,'mianji.out'); rewrite(output); writeln(count); for i:=1 to count do write(s[i],' '); close(output); end.


各种图形面积计算公式

各种图形面积计算公式_教学案例/设计_教学研究_教育专区。各种图形面积计算公式 1、长方形的周长=(长+宽)×2 C=(a+b)×2 2、正方形的周长=边长×4 C=4a ...

各种图形的周长和面积公式

各种图形的周长和面积公式_数学_自然科学_专业资料。各种图形的周长和面积公式...各种面积公式 3页 免费 求下面图形的周长和面积 1页 免费 平面图形的周长...

各种图形面积计算标准方程

各种图形面积计算标准方程_建筑/土木_工程科技_专业资料。土建工程量计算各种图形面积 圆的标准方程 (x-a)2+(y-b)2=r2 注:(a,b)是圆心坐标 圆的一般方程 ...

第十二讲 求图形面积的几种常用方法

第十二讲 求图形面积的几种常用方法 第十二讲 求图形面积的几种常用方法 在组合图形中,求阴影部分的面积的常用方法是:割补法、加减法、旋转法、构造法、 等积...

计算图形面积公式大全

计算图形面积公式大全_初三数学_数学_初中教育_教育专区。很实用的 计算图形面积公式大全 平面图形 名称 正方形 符号 a—边长 周长 C 和面积 S C=4a S=a2 长...

求阴影部分图形面积测试题

求阴影部分图形面积测试题_数学_小学教育_教育专区。经典题型求阴影部分图形面积近年来的中考数学试卷中, 围绕图形面积的知识, 出现了一批考查应用与创新能力的新 题...

平面图形面积计算练习

平面图形面积计算练习_五年级数学_数学_小学教育_教育专区。姓名: 平面图形面积计算练习 1. 如右图,长方形 ABCD 中,BE=4 厘米,CE=3 厘米,长方形的面积是 方...

所有的平面图形的求面积和周长的公式

所有的平面图形求面积和周长的公式_数学_小学教育_教育专区。所有的平面图形求面积和周长的公式: 长方形的周长=(长+宽)× 2 C=(a+b)× 2 2、 正方形...

图形面积计算公式

图形面积计算公式_数学_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档图形面积计算公式_数学_小学教育_教育专区。立体图形面积计算公式 立体图形面积计算...

各种图形面积体积计算公式解释

求面积、 体积公式 1 平面图形面积平面图形面积见表 1-7。 平面图形面积 表 1-7 2 多面体的体积和表面积多面体的体积和表面积见表 1-7。 多面体的体积和...