题解 P1019 【单词接龙】

有楼人上愁 · 2017-12-11 21:47:05 · 题解

一道深搜很好的入门题，可以理解深搜回溯的思想，加一点字符串的技巧。

思路

s[i]是被接的字符串，s[j]是要连接的字串，k是枚举重合的位数。

用的pas函数copy（子串，起始位置，长度）

delete（子串，起始位置，长度）

恕我直言字符串的题pas比c好用

具体看代码

    program dasdsf;
    uses math;
    var s:array[1..22]of string;
    b:array[1..22]of integer;
    //b数组记录次数
    s1,ma:string;//s1是整个操作的字符串
    c:char;
    i,n:longint;
    procedure dfs(i:integer);
    var j,k:integer;
    begin
     if length(s1)>length(ma) then ma:=S1;
     //ma用字符串方便调试，也可以用int
     for j:=1 to n do
      if b[j]<2 then
       for k:=1 to min(length(S[i]),length(s[j]))-1 do//两字串不能重复 故min（s[i],s[j])-1
        if copy(s[i],length(s[i])-k+1,k)=copy(s[j],1,k) then
         begin//标准的回溯
          s1:=s1+copy(s[j],k+1,length(s[j])-k);//连接
          inc(b[j]);//标记
          dfs(j);
          DELETE(s1,length(s1)-(length(s[j])-k)+1,length(s[j])-k);//删除已连接
          dec(b[j]);//释放标记
         end;
    end;
    begin
     read(n);
     readln;
     for i:=1 to n do
      begin
       read(s[i]);
       readln;
      end;
     read(c);
     for i:=1 to n do
      if s[i,1]=c then
       begin//标准的深搜
        s1:=s[i];
        inc(b[i]);
        dfs(i);
        s1:='';
        dec(b[i]);
       end;
      write(length(ma));
    end.