level 5
leavesnight
楼主
代码是spfa+链表:tvvj上面都是写入访问违规runtime error。如果加了assign(input,‘p1232.in’);这种话就是全wa。但是自己拿下数据来测是全对的。。莫名ing。
求懂的人解释下。。
type
ar=array[0..550,0..550] of char;
dr=array[0..270000] of longint;
br=array[0..270000] of boolean;
nextr=^node;
node=record
data:longint;
dis:integer;
next:nextr;
end;
aar=array[0..270000] of nextr;
var
ma:ar;
son:aar;p:nextr;b:br;
q:dr;d:dr;
n,m:integer;num:longint;st,en:longint;
procedure readin;
var i,j,x1,x2,y1,y2:integer;x:longint;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ma[i,j]);
if j>1 then
begin
x:=(i-1)*m+j;
p:=son[x];
new(son[x]);
son[x]^.data:=x-1;
if ma[i,j-1]=ma[i,j] then
son[x]^.dis:=1 else son[x]^.dis:=2;
son[x]^.next:=p;
p:=son[x-1];
new(son[x-1]);
son[x-1]^.data:=x;
son[x-1]^.dis:=son[x]^.dis;
son[x-1]^.next:=p;
end;
if i>1 then
begin
p:=son[x];
new(son[x]);
son[x]^.data:=x-m;
if ma[i-1,j]=ma[i,j] then
son[x]^.dis:=1 else son[x]^.dis:=2;
son[x]^.next:=p;
p:=son[x-m];
new(son[x-m]);
son[x-m]^.data:=x;
son[x-m]^.dis:=son[x]^.dis;
son[x-m]^.next:=p;
end;
end;
readln;
end;
num:=n*m;
read(x1,y1,x2,y2);
st:=(x1-1)*m+y1;
en:=(x2-1)*m+y2;
end;
procedure spfa;
var h,t:int64;zh,zt,x,zc,i:longint;
begin
h:=0;t:=1;
for i:=1 to num do d[i]:=maxlongint-2;
q[1]:=st;
d[st]:=0;
b[x]:=true;
while h<t do
begin
inc(h);
zh:=h mod 260000;
x:=q[zh];
p:=son[x];
while p<>nil do
begin
i:=p^.data;
if d[x]+p^.dis<d[i] then
begin
d[i]:=d[x]+p^.dis;
if not(b[i]) then
begin
inc(t);
zt:=t mod 260000;
q[zt]:=i;
end;
end;
p:=p^.next;
end;
b[x]:=false;
end;
end;
begin
readin;
spfa;
writeln(d[en]);
end.
2010年11月13日 15点11分
1
求懂的人解释下。。
type
ar=array[0..550,0..550] of char;
dr=array[0..270000] of longint;
br=array[0..270000] of boolean;
nextr=^node;
node=record
data:longint;
dis:integer;
next:nextr;
end;
aar=array[0..270000] of nextr;
var
ma:ar;
son:aar;p:nextr;b:br;
q:dr;d:dr;
n,m:integer;num:longint;st,en:longint;
procedure readin;
var i,j,x1,x2,y1,y2:integer;x:longint;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ma[i,j]);
if j>1 then
begin
x:=(i-1)*m+j;
p:=son[x];
new(son[x]);
son[x]^.data:=x-1;
if ma[i,j-1]=ma[i,j] then
son[x]^.dis:=1 else son[x]^.dis:=2;
son[x]^.next:=p;
p:=son[x-1];
new(son[x-1]);
son[x-1]^.data:=x;
son[x-1]^.dis:=son[x]^.dis;
son[x-1]^.next:=p;
end;
if i>1 then
begin
p:=son[x];
new(son[x]);
son[x]^.data:=x-m;
if ma[i-1,j]=ma[i,j] then
son[x]^.dis:=1 else son[x]^.dis:=2;
son[x]^.next:=p;
p:=son[x-m];
new(son[x-m]);
son[x-m]^.data:=x;
son[x-m]^.dis:=son[x]^.dis;
son[x-m]^.next:=p;
end;
end;
readln;
end;
num:=n*m;
read(x1,y1,x2,y2);
st:=(x1-1)*m+y1;
en:=(x2-1)*m+y2;
end;
procedure spfa;
var h,t:int64;zh,zt,x,zc,i:longint;
begin
h:=0;t:=1;
for i:=1 to num do d[i]:=maxlongint-2;
q[1]:=st;
d[st]:=0;
b[x]:=true;
while h<t do
begin
inc(h);
zh:=h mod 260000;
x:=q[zh];
p:=son[x];
while p<>nil do
begin
i:=p^.data;
if d[x]+p^.dis<d[i] then
begin
d[i]:=d[x]+p^.dis;
if not(b[i]) then
begin
inc(t);
zt:=t mod 260000;
q[zt]:=i;
end;
end;
p:=p^.next;
end;
b[x]:=false;
end;
end;
begin
readin;
spfa;
writeln(d[en]);
end.