Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求大牛指导 wa的心惊胆颤//思路是dfs全排列 tle是肯定的 但是没理由wa啊 type map=array[1..31,1..31] of char; var h,w,i,j,t:longint; g,go:map; mark,exi:array['A'..'Z'] of boolean; wor:array[1..26] of char; ans:array[1..26] of char; function search(xmax,xmin,ymax,ymin:longint;st:char):boolean; var i,j:longint; begin for i:=xmin to xmax do begin if (i=xmin) or (i=xmax) then for j:=ymin to ymax do if (g[i,j]<>st) and (g[i,j]<>'?') then exit(false); if (i<>xmax) and (i<>xmin) then if ((g[i,ymin]<>st) and (g[i,ymin]<>'?')) or ((g[i,ymax]<>st) and (g[i,ymax]<>'?')) then exit(false); end; for i:=xmin to xmax do for j:=ymin to ymax do if g[i,j]=st then g[i,j]:='?'; exit(true); end; function flofil(str:char):boolean; var i,j,x,y:longint; xmax,ymax,xmin,ymin:longint; begin xmax:=0; ymax:=0; xmin:=h+1; ymin:=w+1; for i:=1 to h do for j:=1 to w do if g[i,j]=str then begin if i>xmax then xmax:=i; if j>ymax then ymax:=j; if i<xmin then xmin:=i; if j<ymin then ymin:=j; end; if (xmin=h+1) then exit(true); if (xmax-xmin>=2) and (ymax-ymin>=2) then begin if search(xmax,xmin,ymax,ymin,str) then exit(true); end else begin if (xmax-xmin<2) and (ymax-ymin>=2) then begin for x:=1 to h do begin if (x<xmin) and (xmax-x>=2) then if search(x,xmax,ymin,ymax,str) then exit(true); if (x>xmax) and (x-xmin>=2) then if search(xmin,x,ymin,ymax,str) then exit(true); end; end; if (ymax-ymin<2) and (xmax-xmin>=2) then begin for y:=1 to w do begin if (y<ymin) and (ymax-y>=2) then if search(xmin,xmax,y,ymax,str) then exit(true); if (y>ymax) and (y-ymin>=2) then if search(xmin,xmax,ymin,y,str) then exit(true); end; end; if (xmax-xmin<2) and (ymax-ymin<2) then begin for x:=1 to xmax-2 do begin for y:=1 to ymax-2 do if search(x,xmax,y,ymax,str) then exit(true); for y:=xmin+2 to w do if search(x,xmax,ymin,y,str) then exit(true); end; for x:=xmin+2 to h do begin for y:=1 to ymax-2 do if search(x,xmax,y,ymax,str) then exit(true); for y:=xmin+2 to w do if search(x,xmax,ymin,y,str) then exit(true); end; end; end; exit(false); end; procedure dfs(dep:longint); var i:longint; begin if dep=t+1 then begin for i:=t downto 1 do if not flofil(ans[i]) then begin g:=go; exit; end; for i:=1 to t-1 do write(ans[i]); writeln(ans[t]); g:=go; exit; end; for i:=1 to t do if not mark[wor[i]] then begin ans[dep]:=wor[i]; mark[wor[i]]:=true; dfs(dep+1); mark[wor[i]]:=false; end; end; begin assign(input,'p1128.in'); reset(input); assign(output,'p1128.out'); rewrite(output); readln(h,w); t:=0; for i:=1 to h do begin for j:=1 to w do begin read(go[i,j]); if (ord(go[i,j])>=ord('A')) and (not exi[go[i,j]]) then begin inc(t); wor[t]:=go[i,j]; exi[go[i,j]]:=true; end; end; readln; end; g:=go; dfs(1); close(input); close(output); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator