Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 求大牛指导 wa的心惊胆颤

Posted by dujianyi at 2010-06-25 16:53:26 on Problem 1128
//思路是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);
t:=0;
for i:=1 to h do
begin
for j:=1 to w do
begin
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;
end;
g:=go;
dfs(1);
close(input);
close(output);
end.

Followed by: