为什么别人DFS能秒杀我却不能呢？？？？？？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 322ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 306ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 322ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 306ms

├ 测试数据 18：答案正确... 322ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 322ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1900ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 322ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 322ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 353ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 338ms

├ 测试数据 18：答案正确... 369ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 400ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2104ms

数据量很小，与处理后直接floyed.

program lx;

var m,n,i,j,t,k :longint;

d:array[0..500,0..500] of longint;

s1,s0,s:string;

procedure pan;

var o:longint;

begin

o:=0;

if (i1) then

begin if s1[j]s[j] then o:=1;

d[t,t-n]:=o;d[t-n,t]:=o;end;

o:=0;

if (J1) then

begin if s[j]s[j-1] then o:=1;

d[t,t-1]:=o;d[t-1,t]:=o;end;

end;

begin

readln(m,n);

for i:=0 to 500 do for j:=0 to 500 do d:=maxint;

for i:=1 to m do

begin

readln(s);

for j:=1 to n do

begin

t:=t+1;;d[t,t]:=0;

pan;

end;

s1:=s;if i=1 then s0:=s;

end;

for k:=1 to t do

for i:=1 to t do

if ki then

for j:=1 to t do

if (ij)and(kj) then

begin

if d+d[k,j]

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

自己都不知道用了什么方法。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DFS!!!不过不能直接DIJKSTRA！WA了一次！

编译错误！！！！！！！！！！！！...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：100000000000000year

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

program p1406;

const maxn=200;

gx:array[1..4] of integer=(0,1,0,-1);

gy:array[1..4] of integer=(1,0,-1,0);

var i,j,k,m,n,ans:longint;

dis:array[1..maxn,1..maxn] of longint;

pic:array[0..maxn,0..maxn] of char;

visit:array[0..maxn,0..maxn] of boolean;

procedure init;

var i,j:longint;

begin

fillchar(pic,sizeof(pic),0);

fillchar(dis,sizeof(dis),0);

readln(m,n);

for i:=1 to m do begin

for j:=1 to n do

read(pic);

readln;

end;

ans:=maxlongint;

end;

procedure dfs(x,y,l:Longint);

var i,j,k:longint;

begin

visit[x,y]:=true;

dis[x,y]:=l;

for i:=1 to 4 do

begin

j:=x+gx[i]; k:=y+gy[i];

if ((j0)and(k0)) then begin

if ((pic[j,k]=pic[x,y])and((l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 633ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 618ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 618ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 633ms

├ 测试数据 18：答案正确... 618ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 618ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3738ms

裸FLOYD，时间很整齐。。。

秒杀过....要是数据大一点就不能了吧.....

直接记忆化

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

记忆化DFS.

很快的.

而且代码很好写.

Floodfill+Dijikstra代码有点长..

program aa

procedure dfs(x,y,w:longint);

begin

　　b[x,y]:=true;

　　inc(r);

　　p[r]:=x;q[r]:=y;f[x,y]:=w;

　　if (a[x-1,y]=a[x,y])and(not b[x-1,y])then dfs(x-1,y,w);

　　if (a[x,y-1]=a[x,y])and(not b[x,y-1])then dfs(x,y-1,w);

　　if (a[x+1,y]=a[x,y])and(not b[x+1,y])then dfs(x+1,y,w);

　　if (a[x,y+1]=a[x,y])and(not b[x,y+1])then dfs(x,y+1,w)

end;

for i:=1 to m do if not b[1,i]then dfs(1,i,1);

l:=1;

while l1)and(not b[p[l]-1,q[l]])then dfs(p[l]-1,q[l],f[p[l],q[l]]+1);

　　 if (p[l]1)and(not b[p[l],q[l]-1])then dfs(p[l],q[l]-1,f[p[l],q[l]]+1);

　　 if (q[l]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

纪念下···

感谢楼下的 IEK

``记忆直接DFS进去。

一开始吧X,Y弄反了。。

郁闷了好久。。

FILLDWORD忘记了 DIV 4.

今天RP这么低。。

LP不稳定。有一次95分。。

Floodfill，然后构图，找最短路

找出题目中隐含的关系：如果相邻两点不同，则代价1，相同则代价0。转化成最短路问题。

解法1: Floodfill+dijkstra

先用floodfill把每个区间都标上号，然后扫描一遍，如果两个不同区间相连就把权设成1吧。为了方便起见，设一个源点和汇点（我的程序里面是在最上面和最下面都加了一行），做dijkstra。

const

d:array[1..4,1..2]of longint=((0,1),(0,-1),(1,0),(-1,0));

var

i,j,k,l,m,n,now,ii,jj,s,min:longint;

a:array[-1..23,-1..23]of char;

num:array[-1..23,-1..23]of longint;

aa:array[1..500,1..500]of longint;

dd:array[1..500]of longint;

v:array[1..500]of boolean;

procedure dfs(x,y,ss:longint);

var

i,xx,yy:longint;

begin

num[x,y]:=ss;

for i:=1 to 4 do

begin

xx:=x+d; yy:=y+d;

if (num[xx,yy]=-1)and(a[xx,yy]=a[x,y]) then dfs(xx,yy,ss);

end;

end;

begin

assign(input,'1406.in');reset(input);

readln(n,m);

for i:=-1 to 23 do for j:=-1 to 23 do a:='-';

for j:=1 to m do begin a[0,j]:='0'; a[n+1,j]:='0'; end;

for i:=1 to n do

begin

for j:=1 to m do read(a);

readln;

end;

now:=0;

fillchar(num,sizeof(num),$FF);

for i:=0 to n+1 do

for j:=1 to m do

if num=-1 then begin inc(now); dfs(i,j,now); end;

for i:=0 to n+1 do

for j:=1 to m do

for k:=1 to 4 do

begin

ii:=i+d[k,1]; jj:=j+d[k,2];

if (a[ii,jj]a)and(a[ii,jj]'-') then aa[num,num[ii,jj]]:=1;

end;

{dijkstra}

fillchar(v,sizeof(v),false);

fillchar(dd,sizeof(dd),0);

s:=1; v:=true;

repeat

m:=maxlongint; k:=0;

for i:=1 to now do

begin

if (aa=1)and((dd+aa

这是一个很隐蔽的最短路径问题……

相邻结点，如果字母相同则表示距离为 0，否则就是 1

把第一行结点全放入优先队列，然后……

DP...

就是用FLOODFILL实现的记忆化搜索的DP...

跟清帝之惑的滑雪差不多...

要不要环行队列MS都可以

因为我是猥琐男,所以我用了猥琐的广搜套深搜的方法...39行Code

procedure dfs(x,y,w:longint);

begin

b[x,y]:=true;

inc(r);

p[r]:=x;q[r]:=y;f[x,y]:=w;

if (a[x-1,y]=a[x,y])and(not b[x-1,y])then dfs(x-1,y,w);

if (a[x,y-1]=a[x,y])and(not b[x,y-1])then dfs(x,y-1,w);

if (a[x+1,y]=a[x,y])and(not b[x+1,y])then dfs(x+1,y,w);

if (a[x,y+1]=a[x,y])and(not b[x,y+1])then dfs(x,y+1,w)

end;

for i:=1 to m do if not b[1,i]then dfs(1,i,1);

l:=1;

while l1)and(not b[p[l]-1,q[l]])then dfs(p[l]-1,q[l],f[p[l],q[l]]+1);

if (p[l]1)and(not b[p[l],q[l]-1])then dfs(p[l],q[l]-1,f[p[l],q[l]]+1);

if (q[l]

看到这个题下面的大牛有用DP和图做的，实在太强了。

这个题我是用深搜做的，只加了一个小小的剪枝。我的搜索结构很简单，就是每一步个向四个方向搜，然后记录到每个点最小步数，每次搜到这个点就更新最小值。

大体如下：

for i:=1 to 4 do

begin

xx:=dx[i]+x; yy:=dy[i]+y;

if not vis[xx][yy] then

begin

vis[xx][yy]:=true;

if dat[xx][yy]=dat[x][y] then//相同

if ans[xx][yy]>ans[x][y] then//当下一个点不如这个优时DFS

begin

ans[xx][yy]:=ans[x][y];

dfs(xx,yy);

end;

if dat[xx][yy]dat[x][y] then

if ans[xx][yy]>ans[x][y]+1 then

begin

ans[xx][yy]:=ans[x][y]+1;//步数加一

if ans[xx][yy]