| |
|
本题表述了一个三维空间的问题，其本质是求一个图中的连同分量。
这个图以象素为顶点，如果任意两个相邻象素的差的绝对值不大于M，则在代表这两个像素的顶点间连一条边。建图以后可以发现，原题目中所描述的一个部件其实就是图中的一个连同分量，只需要遍历一遍图就可求出连同分量的个数。
算法流程如下：
for x := 1 to L do
for y := 1 to W do
for z := 1 to H do
if 象素(x, y, z) 还未被标记 then
begin
部件数加1
扩展象素(x, y, z)所在的部件并标记该部件内的所有象素（广度搜索）
end
程序清单如下：
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
const
ifn = 'scan.in';
ofn = 'scan.out';
maxsize = 50;
dx: array[1..6] of integer = (0, 0, 1, 0, 0, -1);
dy: array[1..6] of integer = (0, 1, 0, 0, -1, 0);
dz: array[1..6] of integer = (1, 0, 0, -1, 0, 0);
type
Ptwo = ^Ttwo;
Ttwo = array[1..maxsize, 1..maxsize] of integer;
Pnode = ^Tnode;
Tnode = record
x, y, z: integer;
next: Pnode;
end;
var
three: array[1..maxsize] of Ptwo;
l, w, h, m: integer;
total: longint;
procedure init;
var
x, y, z: integer;
begin
assign(input, ifn);
reset(input);
readln(l, w, h);
readln(m);
for x := 1 to l do
begin
new(three[x]);
fillchar(three[x]^, sizeof(three[x]^), 0);
for y := 1 to w do
for z := 1 to h do
begin
read(three[x]^[y, z]);
inc(three[x]^[y, z]);
end;
end;
close(input);
end;
procedure fill(var node: Pnode; x, y, z: integer);
begin
new(node);
node^.x := x;
node^.y := y;
node^.z := z;
node^.next := nil;
three[x]^[y, z] := - three[x]^[y, z];
end;
procedure expand(x, y, z: integer);
var
x2, y2, z2, i, key: integer;
head, tail, temp: Pnode;
begin
fill(head, x, y, z);
tail := head;
repeat
key := - three[head^.x]^[head^.y, head^.z];
for i := 1 to 6 do
begin
x2 := head^.x + dx[i];
y2 := head^.y + dy[i];
z2 := head^.z + dz[i];
if (x2 > 0) and (x2 <= l) and (y2 > 0) and (y2 <= w) and
(z2 > 0) and (z2 <= h) and (three[x2]^[y2, z2] > 0) and
(abs(key - three[x2]^[y2, z2]) <= m) then
begin
fill(tail^.next, x2, y2, z2);
tail := tail^.next;
end;
end;
temp := head;
head := head^.next;
dispose(temp);
until head = nil;
end;
procedure main;
var
x, y, z: integer;
begin
total := 0;
for x := 1 to l do
for y := 1 to w do
for z := 1 to h do
if three[x]^[y, z] > 0 then
begin
inc(total);
expand(x, y, z);
end;
end;
procedure show;
begin
assign(output, ofn);
rewrite(output);
writeln(total);
close(output);
end;
begin
init;
main;
show;
end.
|
|
|
