首页| 论坛| 消息
主题:看你的广搜水平怎么样?答案稍后公布
realmans发表于 2010-06-12 07:49
【问题描述】小鼠a与小鼠b身处一个m×n的迷宫中,如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的,不允许任何人进入。在迷宫中任何位置均可沿上,下,左,右4个方向进入未封闭的房间。小鼠a位于迷宫的(p,q)方格中,它必须找出一条通向小鼠b所在的(r,s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。
输入:输入数据第一行有3个正整数n,m,k,分别表示迷宫的行数,列数和封闭的房间数。接下来的k行中,每行2个正整数,表示被封闭的房间所在的行号和列号。最后的2行,每行也有2个正整数,分别表示小鼠a所处的方格(p,q)和小鼠 b 所处的方格(r,s)。
输出:小鼠a通向小鼠b有多少条不同的最短路。如果小鼠a无法通向小鼠b则输出“NoSolution!”。
提示:采用广度优先搜索解决本题。二维数组g存储最短路长度,二维数组tot存储最短路条数。
【输入输出样例】
输入:884 输出:8
12
37
55
82
33
66
program ex6;
const
dis:array[0..3,0..1] of integer=((0,-1),(0,1),(1,0),(-1,0));
var
n,m,k,q,p,r,s:integer;
g,tot:array[0..200,0..200] of integer;
list:array[0..40000,0..1] of integer;
op,cl:integer;
i,j,t,x,y,nx,ny,step:longint;
finish:boolean;
begin
readln(n,m,k);
fillchar(g,sizeof(g),0); fillchar(tot,sizeof(tot),0);
finish:=false;
for t:=0 to k-1 do begin
readln(i,j);
____________
end;
readln(p,q); readln(r,s);
c1:=1; op:=1;
list[1,0]:=p; list[1,1]:=q;
tot:=1; step:=999999;
while (______) do begin
x:=list; y:=list;
for i:=0 to 3 do begin
nx:=x+dis; ny:=y+dis;
if (nxn) or (nym) then continue;
if (g= -1) then continue;
if (tot0) then begin
_________
continue;
end;
inc(op);
list:=nx; list:=
下一页 (1/2)
回帖(1):
1楼:这个是上题图片,http://218.4.165.132/oj/ShowProblem?problemid=c007

--> 全部回帖(1)»
最新回帖
收藏本帖
发新帖