Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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);
  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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator