Poj1072 Puzzle Out — DFS+Trie+剪枝

Note: 本文最初于 2011年03月02日 星期三 18:07 在 hi.baidu.com/lydrainbowcat 发表。š

附:本题测试数据：http://icpc.baylor.edu/past/icpc2002/regionals/Tehran01/problems.html

本题算是一道比较有一些难度的搜索题目。单单使用DFS肯定是会TLE的，所以我们应该使用Trie优化。

难点：1.DFS的函数结构怎样设计。2.如何剪枝避免TLE。

思路：用Trie存字典，然后每次找出空余未知字母最少的一个单词（第一个单词找最长的比较好），Trie从顶向下搜索，遇到矛盾则退出，直到该单词确定，然后搜索下一个单词，直到所有单词都被确定或者No Solution。注意失败的时候还原现场的处理。当ans>1时直接退出输出More Solution。

Source Code

Problem: 1072		User: lydliyudong
Memory: 17124K		Time: 360MS
Language: Pascal		Result: Accepted

• Source Code

type
 dic=array['A'..'Z']of char;
var
 trie:array[0..350000,'A'..'Z']of longint;{向下的指针}
 len:array[0..350000,0..20]of boolean;
 b:array[0..10000]of string;{待解密单词}
 key:array[0..10000]of boolean;{是否被解密过}
 d,f,v:dic;//字典
 n,m,w,tot,l,ans,now,u:longint;
 s,st:ansistring;

procedure sort;
 var
  i,j,k:longint;
 begin
  for i:=1 to w-1 do
   for j:=i+1 to w do
    if length(b[i])<length(b[j]) then
     begin st:=b[i]; b[i]:=b[j]; b[j]:=st; end;
 end;

procedure insert(num,p:longint);
 begin
  len[num,l]:=true;
  if p=l+1 then exit;
  if trie[num,s[p]]<>0 then insert(trie[num,s[p]],p+1)
  else begin
   inc(tot);
   trie[num,s[p]]:=tot;
   insert(tot,p+1);
  end;
 end;

procedure scanf;
 var
  j:longint;
 begin
  readln(s);
  while s<>'' do//读入处理
   begin
    while s[length(s)]=' ' do delete(s,length(s),1);
    j:=2;
    while j<=length(s) do
     if (s[j]=' ')and(s[j-1]=' ') then delete(s,j-1,1) else inc(j);
    st:='';
    for j:=1 to length(s) do
     if s[j]<>' ' then st:=st+s[j]
      else if s[j]=' ' then begin
       inc(w);
       b[w]:=st;
       st:='';
      end;{else}
    inc(w); b[w]:=st;
    readln(s);
   end;{while}
 end;

procedure scan;
 var
  i:longint;
 begin
  readln(n);
  for i:=1 to n do
   begin
    readln(s);
    l:=length(s);
    insert(0,1);
   end;
  readln(m);
  readln(s);
 end;


function find:longint;
 var
  min,i,j,k:longint;
 begin
  min:=maxint;
  find:=0;
  for i:=1 to w do
   if not key[i] and(b[i]<>'') then
    begin
     k:=0;
     for j:=1 to length(b[i]) do
      if v[b[i,j]]='*' then inc(k);
     if k<min then begin min:=k; find:=i; end;
    end;
 end;

procedure dfs(step,now,num,p,l:longint);
 var
  ch:char;
  red,rev:dic;
  k:longint;
 begin
  if step=w+1 then
   begin
    inc(ans);
    if ans=1 then f:=d;
    exit;
   end;
  if p=l+1 then
   begin
    k:=0;
    k:=find;
    key[k]:=true;
    dfs(step+1,k,0,1,length(b[k]));
    if ans>1 then exit;
    key[k]:=false;
   end;
  for ch:='A' to 'Z' do
   if len[trie[num,ch],l] and(trie[num,ch]<>0) then
    if ((d[ch]='*')or(d[ch]=b[now,p]))and((v[b[now,p]]='*')or(v[b[now,p]]=ch)) then
     begin
      red:=d; rev:=v;
      d[ch]:=b[now,p];
      v[b[now,p]]:=ch;
      dfs(step,now,trie[num,ch],p+1,l);
      if ans>1 then exit;
      d:=red; v:=rev;
     end;
 end;


procedure puzzle_out;
 var
  ch:char;
  i,j,max:longint;
 begin
  scan;
  for i:=1 to m do
   begin
    w:=0;
    scanf;
    sort;
    for ch:='A' to 'Z' do begin d[ch]:='*'; v[ch]:='*'; end;
    fillchar(key,sizeof(key),0);
    ans:=0;
    key[1]:=true;
    dfs(1,1,0,1,length(b[1]));
    if ans=0 then writeln('#No solution#');
    if ans=2 then writeln('#More than one solution#');
    if ans=1 then
     begin for ch:='A' to 'Z' do write(f[ch]); writeln; end;
   end;{for i}
 end;

begin
 puzzle_out;
end.