今天的文件夹：10月19日.zip
今天中午讲了一下昨天的题，还是有水平的。
下午复习搜索，居然有NOI难度的题，不过给了讲解，也有参考程序，就不多说了。主要说说第一题。
T1:这是道BFS练手题，但都写不对。第一个难点是读入，虽然题目中给的读入顺序很吓人，但仔细想想，就类似于“字典序比较”了。在Pascal中可以直接这样读入：
for i:=1 to l do for j:=1 to w do for k:=1 to h do read(a[i,j,k]);
读入之后，按照与读入相同的顺序进行查找，找到第一个未被标记的点，然后以它为起点做一次BFS（搜索中注意及时更新标记，把所有可以判断为同一区域的点标记下来）。做完这一次BFS，标记已被更新，从上次的位置开始继续查找。这样找过一遍之后，可以保证所有点都被标记，统计所有BFS起点的个数即可。
代码：
1 program scan; 2 var 3 l,w,h,m:longint; 4 a,b:array[-1..51,-1..51,-1..51] of longint; 5 i,j,k:byte; 6 n,left,right:longint; 7 x0,y0,z0:byte; 8 queue:array[1..1000000,1..3] of byte; 9 procedure clear(); 10 begin 11 left:=1; 12 right:=0; 13 end; 14 procedure enque(x,y,z:longint); 15 begin 16 inc(right); 17 queue[right,1]:=x; 18 queue[right,2]:=y; 19 queue[right,3]:=z; 20 b[x,y,z]:=n; 21 end; 22 procedure deque(); 23 begin 24 inc(left); 25 end; 26 function check(t:longint):boolean; 27 begin 28 if (x0<1)or(x0>l)or(y0<1)or(y0>W)or(z0<1)or(z0>h) then 29 exit(false); 30 if b[x0,y0,z0]>0 then 31 exit(false); 32 if abs(a[x0,y0,z0]-t)<=m then 33 exit(true) 34 else 35 exit(false); 36 end; 37 procedure bfs(x,y,z:longint); 38 begin 39 clear(); 40 enque(x,y,z); 41 while (left<=right) do 42 begin 43 x:=queue[left,1]; 44 y:=queue[left,2]; 45 z:=queue[left,3]; 46 deque(); 47 x0:=x-1; y0:=y; z0:=z; 48 if check(a[x,y,z]) then 49 enque(x0,y0,z0); 50 x0:=x+1; y0:=y; z0:=z; 51 if check(a[x,y,z]) then 52 enque(x0,y0,z0); 53 x0:=x; y0:=y-1; z0:=z; 54 if check(a[x,y,z]) then 55 enque(x0,y0,z0); 56 x0:=x; y0:=y+1; z0:=z; 57 if check(a[x,y,z]) then 58 enque(x0,y0,z0); 59 x0:=x; y0:=y; z0:=z-1; 60 if check(a[x,y,z]) then 61 enque(x0,y0,z0); 62 x0:=x; y0:=y; z0:=z+1; 63 if check(a[x,y,z]) then 64 enque(x0,y0,z0); 65 end; 66 end; 67 begin 68 assign(input,'scan.in'); 69 reset(input); 70 assign(output,'scan.out'); 71 rewrite(output); 72 readln(l,w,h,m); 73 for i:=1 to l do 74 for j:=1 to w do 75 for k:=1 to h do 76 read(a[i,j,k]); 77 fillchar(b,sizeof(b),0); 78 n:=0; 79 for i:=1 to l do 80 for j:=1 to w do 81 for k:=1 to h do 82 if b[i,j,k]=0 then 83 begin 84 inc(n); 85 bfs(i,j,k); 86 end; 87 writeln(n); 88 close(input); 89 close(output); 90 end. |
