首页 > 代码库 > 二、搜索
二、搜索
1.红与黑（codevs2806）
题目网址：http://codevs.cn/problem/2806/
代码：
var
s:array[0..21,0..21] of char;
i,j,sum,w,c,x,y:longint;
procedure m(a,b:longint);
begin
inc(sum);
s[a,b]:=‘#‘;
if(s[a+1,b]=‘.‘) then
begin
m(a+1,b);
end;
if(s[a-1,b]=‘.‘) then
begin
m(a-1,b);
end;
if(s[a,b+1]=‘.‘) then
begin
m(a,b+1);
end;
if(s[a,b-1]=‘.‘) then
begin
m(a,b-1);
end;
end;
begin
readln(w,c);
while (w<>0) and (c<>0) do
begin
fillchar(s,sizeof(s),0);
for i:=1 to c do
begin
for j:=1 to w do
begin
read(s[i,j]);
if (s[i,j]=‘@‘) then
begin
x:=i;
y:=j;
end;
end;
readln;
end;
sum:=0;
m(x,y);
writeln(sum);
readln(w,c);
end;
end.
2.八数码难题
题目网址：http://codevs.cn/problem/1225/
分析：
这题值得说的是康托展开。全排列与整数的映射，挺实用的。
接下来就是普通的BFS了。和用HASH表判重
代码：
type arr=array [1..9] of longint;var a:array [1..30000] of arr;
fac:array [0..10] of longint;
step,space:array [0..30000] of longint;
i,front,tail:longint;
s:string;
hash:array [1..400000] of boolean;
function cantor(a:arr):longint;
var i,j:longint;
k:arr;
begin
fillchar(k,sizeof(k),0);
cantor:=0;
for i:=1 to 9 do
for j:=i+1 to 9 do
if a[i]>a[j] then inc(k[i]);
for i:=1 to 9 do cantor:=cantor+k[i]*fac[9-i];
cantor:=cantor+1;
end;
procedure exchange(s,t:longint);
var tmp:arr;
num,fun,i:longint;
begin
tmp:=a[front];
fun:=tmp[s]; tmp[s]:=tmp[t];tmp[t]:=fun;
num:=cantor(tmp);
if num=46686 then
begin
write(step[front]+1);
halt;
end;
if not hash[num] then
begin
inc(tail);
a[tail]:=tmp;
hash[num]:=true;
space[tail]:=t;
step[tail]:=step[front]+1;
end;
end;
begin
fillchar(hash,sizeof(hash),false);
readln(s);
fac[0]:=1;
for i:=1 to 9 do fac[i]:=i*fac[i-1];
for i:=1 to 9 do
begin
a[1][i]:=ord(s[i])-ord(‘0‘);
if a[1][i]=0 then space[1]:=i;
end;
hash[cantor(a[1])]:=true;
front:=1;
tail:=1;
step[1]:=0;
while front<=tail do
begin
if space[front]<=6 then exchange(space[front],space[front]+3);
if space[front]>=4 then exchange(space[front],space[front]-3);
if ((space[front]-1)mod 3)>0 then exchange(space[front],space[front]-1);
if ((space[front]-1)mod 3)<2 then exchange(space[front],space[front]+1);
inc(front);
end;
end.
题目网址：http://codevs.cn/problem/1411/
分析：利用BFS求无权最短路径
代码：
var
a:array[1..150,1..150] of char;
b:array[1..22500,1..3] of longint;
i,j,m,n,x,y,m1,n1,m2,n2,f,r:longint;
begin
readln(n,m);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(a[i,j]);
if a[i,j]=‘K‘ then
begin
m1:=i;
n1:=j;
end;
if a[i,j]=‘H‘ then
begin
m2:=i;
n2:=j;
end;
end;
readln;
end;
f:=1;
r:=1;
a[m2,n2]:=‘*‘;
b[f,1]:=m2;
b[f,2]:=n2;
b[f,3]:=0;
repeat
x:=b[f,1];
y:=b[f,2];
if (x=m1) and (y=n1) then
begin
writeln(b[f,3]);
end;
if (x-1>0) and (y-2>0) and (a[x-1,y-2]<>‘*‘) then
begin
inc(r);
b[r,1]:=x-1;
b[r,2]:=y-2;
b[r,3]:=b[f,3]+1;
a[x-1,y-2]:=‘*‘;
end;
if (x-2>0) and (y-1>0) and (a[x-2,y-1]<>‘*‘) then
begin
inc(r);
b[r,1]:=x-2;
b[r,2]:=y-1;
b[r,3]:=b[f,3]+1;
a[x-2,y-1]:=‘*‘;
end;
if (x-2>0) and (y+1<n) and (a[x-2,y+1]<>‘*‘) then
begin
inc(r);
b[r,1]:=x-2;
b[r,2]:=y+1;
b[r,3]:=b[f,3]+1;
a[x-2,y+1]:=‘*‘;
end;
if (x-1>0) and (y+2<n) and (a[x-1,y+2]<>‘*‘) then
begin
inc(r);
b[r,1]:=x-1;
b[r,2]:=y+2;
b[r,3]:=b[f,3]+1;
a[x-1,y+2]:=‘*‘;
end;
if (x+1<m) and (y-2>0) and (a[x+1,y-2]<>‘*‘) then
begin
inc(r);
b[r,1]:=x+1;
b[r,2]:=y-2;
b[r,3]:=b[f,3]+1;
a[x+1,y-2]:=‘*‘;
end;
if (x+2<m) and (y+1<n) and (a[x+2,y+1]<>‘*‘) then
begin
inc(r);
b[r,1]:=x+2;
b[r,2]:=y+1;
b[r,3]:=b[f,3]+1;
a[x+2,y+1]:=‘*‘;
end;
if (x+2<m) and (y-1>0) and (a[x+2,y-1]<>‘*‘) then
begin
inc(r);
b[r,1]:=x+2;
b[r,2]:=y-1;
b[r,3]:=b[f,3]+1;
a[x+2,y-1]:=‘*‘;
end;
if (x+1<m) and (y+2<n) and (a[x+1,y+2]<>‘*‘) then
begin
inc(r);
b[r,1]:=x+1;
b[r,2]:=y+2;
b[r,3]:=b[f,3]+1;
a[x+1,y+2]:=‘*‘;
end;
inc(f);
until f>r;
end.
4.最大黑区域
描写叙述：
二值图像是由黑白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完毕二值图像的这个操作。黑区域由黑像素组成。一个黑区域中的每一个像素至少与该区域中的还有一个像素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。
一个黑区域的面积是其所包括的像素的个数。
输入格式：
输入由多个測试例组成。
每一个測试例的第一行含两个整数n和m, (1 <=n,m<=100), 分别表示二值图像的行数与列数，后面紧跟着n行，每行含m个整数0或1，当中第i行表示图像的第i行的m个像素，0表示白像素，1表示黑像素。
同一行的相邻两个整数之间用一个空格隔开，两个測试例之间用一个空行隔开，最后一个測试例之后隔一个空行，再接的一行含有两个整数0，标志输入的结束。
输出格式:
每一个測试例相应一行输出，含一个整数，表示相应的图像中最大黑区域的面积。
输入例子：
5 6
0 1 1 0 0 1
1 1 0 1 0 1
0 1 0 0 1 0
0 0 0 1 1 1
1 0 1 1 1 0
0 0
输出例子：
7
分析：利用BFS求连通块
代码：
var
a:array [1..101,1..101] of 0..1;
f:array [1..101,1..101] of boolean;
i,j,n,m,x,m1,n1,max:longint;
ch:string;
procedure js(m1,n1:longint);
begin
if (m1>m) or (n1>n) then exit;
a[m1,n1]:=0;
if (m1>1)and(a[m1-1,n1]<>0) then
begin
js(m1-1,n1);
end;
if (n1>1)and(a[m1,n1-1]<>0) then
begin
js(m1,n1-1);
end;
if (a[m1,n1+1]<>0) then
begin
js(m1,n1+1);
end;
if (a[m1+1,n1]<>0) then
begin
js(m1+1,n1);
end;
inc(x);
exit;
end;
begin
max:=0;
x:=0;
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(a[i,j]);
end;
readln;
end;
for i:=1 to m do
begin
for j:=1 to n do
begin
if a[i,j]<>0 then js(i,j);
if max<x then max:=x;
x:=0;
end;
end;
writeln(max);
end.
5.解救ice-cream
描写叙述 Description
给你一张坐标图，s为Tina的初始位置。m为Ice-cream home的位置。‘.’为路面，Tina在上面，每单位时间能够移动一格；‘#’为草地，Tina在上面，每两单位时间能够移动一格（建议不要模仿—毕竟Tina还小）；‘o’是障碍物，Tina不能在它上面行动。也就是说，Tina仅仅能在路面或草地上行走，必须绕过障碍物。并到达冰淇淋店。但是…………不保证到达时，冰淇淋还未融化，所以……就请聪明的你……选择最佳的方案啦…………假设。Tina到的时候，冰淇淋已经融化完了，那她但是会哭的。
输入格式 Input Format
依次输入冰淇淋的融化时间t(0<t<1000)，坐标图的长x,宽y(5<=x,y<=25){太长打起来好累……}，和整张坐标图。
输出格式 Output Format
推断依照最优方案能否够赶在冰淇淋融化之前到达冰淇淋店（注：当T=最优方案所用时间，则推断为未赶到），如赶到，输出所用时间；如未赶到。输出Tina的哭声——“55555”（不包含引號）。
例子输入 Sample Input
11
10
8
......s...
..........
#ooooooo.o
#.........
#.........
#.........
#.....m...
#.........
例子输出 Sample Output
10
时间限制 Time Limitation
各个測试点1s
分析：利用BFS求加权单源最佳路径
借用王大牛代码：program P1340;
type
rec=record
x,y:longint;
di:longint;
time:longint;
end;
var
s:array[1..100000,1..4] of longint;
time:array[1..30,1..30] of longint;
a:array[1..30,1..30] of char;
sb1,sb2:char;
b:array[1..30,1..30] of longint;
q,open,closed,t,x,y,x0,y0,x1,y1,i,j,k,l,m:longint;
begin
q:=maxlongint;
assign(input,‘haha.in‘);
reset(input);
readln(t);
read(x,y);
for j:=1 to y do
begin
read(sb1,sb2);
for i:=1 to x do
begin
read(a[i,j]);
if a[i,j]=‘.‘then b[i,j]:=1
else if a[i,j]=‘#‘then b[i,j]:=2
else if a[i,j]=‘o‘ then b[i,j]:=maxlongint
else if a[i,j]=‘s‘ then begin x0:=i;y0:=j; b[i,j]:=1;end
else if a[i,j]=‘m‘ then begin x1:=i;y1:=j; b[i,j]:=0;end;
end;
end;
close(input);
for j:=1 to y do
for i:=1 to x do
time[i,j]:=maxlongint;
closed:=0; open:=1;
s[1,1]:=x0; s[1,2]:=y0; s[1,3]:=0; s[1,4]:=0;
repeat
repeat
inc(closed);
if time[s[closed,1],s[closed,2]]>s[closed,4] then begin
time[s[closed,1],s[closed,2]]:=s[closed,4];
if (s[closed,3]<>1)and(s[closed,1]<x)and(a[s[closed,1]+1,s[closed,2]]<>‘o‘)then begin
inc(open);
s[open,1]:=s[closed,1]+1;
s[open,2]:=s[closed,2];
s[open,3]:=3;
s[open,4]:=s[closed,4]+b[s[closed,1],s[closed,2]];
end;
if a[s[open,1],s[open,2]]=‘m‘ then break;
if (s[closed,3]<>3)and(s[closed,1]>1)and(a[s[closed,1]-1,s[closed,2]]<>‘o‘) then begin
inc(open);
s[open,1]:=s[closed,1]-1;
s[open,2]:=s[closed,2];
s[open,3]:=1;
s[open,4]:=s[closed,4]+b[s[closed,1],s[closed,2]];
end;
if a[s[open,1],s[open,2]]=‘m‘ then break;
if (s[closed,3]<>0)and(s[closed,2]>1)and(a[s[closed,1],s[closed,2]-1]<>‘o‘) then begin
inc(open);
s[open,1]:=s[closed,1];
s[open,2]:=s[closed,2]-1;
s[open,3]:=2;
s[open,4]:=s[closed,4]+b[s[closed,1],s[closed,2]];
end;
if a[s[open,1],s[open,2]]=‘m‘ then break;
if (s[closed,3]<>2)and(s[closed,2]<y)and(a[s[closed,1],s[closed,2]+1]<>‘o‘) then begin
inc(open);
s[open,1]:=s[closed,1];
s[open,2]:=s[closed,2]+1;
s[open,3]:=0;
s[open,4]:=s[closed,4]+b[s[closed,1],s[closed,2]];
end;
if a[s[open,1],s[open,2]]=‘m‘ then break;
end;
until (a[s[open,1],s[open,2]]=‘m‘)or(closed=open);
if q>s[open,4] then q:=s[open,4];
until (closed=open);
if q>=t then write(‘55555‘)
else
write(q);
end.
二、搜索