P1560 蜗牛的旅行

本文主要是介绍P1560 蜗牛的旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题是找最多走过了格数，可以用dfs

const z:array[1..4,1..2]of -1..1=((0,1),(0,-1),(1,0),(-1,0));//呀，方便啊
var i,j,k,x,y:longint;m,n,max:longint;a:array[0..200,0..200]of 0..2;//记录所用的表格s:string;
procedure dfs(x,y,fx,sum:longint);//DFS-QAQ
var i,j:longint;
beginif a[x,y]=1 thenbeginif sum>max then max:=sum;if a[x+z[fx,1],y+z[fx,2]]=1 then//如果可以的话一直向前走QAQbegina[x,y]:=2;dfs(x+z[fx,1],y+z[fx,2],fx,sum+1);//dfsa[x,y]:=1;endelsebegina[x,y]:=2;if a[x+z[fx,1],y+z[fx,2]]=0 thenbeginif fx in [1..2] then//根据方向查找，不可以走相反方向和相同方向beginif a[x+z[4,1],y+z[4,2]]=1 thendfs(x+z[4,1],y+z[4,2],4,sum+1);//dfsif a[x+z[3,1],y+z[3,2]]=1 thendfs(x+z[3,1],y+z[3,2],3,sum+1);//dfsendelsebeginif a[x+z[1,1],y+z[1,2]]=1 thendfs(x+z[1,1],y+z[1,2],1,sum+1);//dfsif a[x+z[2,1],y+z[2,2]]=1 thendfs(x+z[2,1],y+z[2,2],2,sum+1);//dfs__QAQend;end;a[x,y]:=1;//已经走过了end;end;
end;
beginread(n,m);for i:=1 to n dofor j:=1 to n doa[i,j]:=1;readln;for i:=1 to m dobeginreadln(s);//读入麻烦一点x:=ord(s[1])-ord('A')+1;y:=ord(s[2])-ord('0');if length(s)>=3 theny:=y*10+ord(s[3])-ord('0');if length(s)>=4 theny:=y*10+ord(s[4])-ord('0');a[y,x]:=0;end;for i:=1 to 4 do//四个方向查找begindfs(1,1,i,1);end;write(max);//输出最大的解就可以了QAQ
end.

平时BFS写多了，来一道DFS也不错

这篇关于P1560 蜗牛的旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---