ctrl+a+ctrl+c+ctrl+v+alt+s的人自重>_<
const all=1048575;
type
	pack =record
			state,len:longint;
		end;
	queue=object
			private q:array[0..all] of pack;
			private hash:array[0..all] of longint;
			private place:array[0..all] of longint;
			private head,tail,curid:longint;
			private function exist(const key,len:longint):boolean;
			public procedure clear();
			public procedure init();
			public procedure insert(const key,len:longint);
			public function gethead():pack;
			public function empty():boolean;
			public procedure update();
		end;
	pointer=^queue;

function make_pair(const x,y:longint):pack;
begin with make_pair do
	begin state:=x;
		len:=y;
	end;
end;

function queue.exist(const key,len:longint):boolean;
begin if hash[key]=curid then
	begin if len<q[place[key]].len then q[place[key]].len:=len;
		exit(true);
	 end
	else begin
		hash[key]:=curid; place[key]:=tail;
		exit(false);
	end;
end;

procedure queue.clear();
begin inc(curid); head:=0; tail:=0; end;

procedure queue.init();
begin curid:=0;
	fillchar(hash,sizeof(hash),0);
	clear();
end;

procedure queue.insert(const key,len:longint);
begin if exist(key,len) then exit;
	q[tail]:=make_pair(key,len); inc(tail);
end;

function queue.gethead():pack;
begin gethead:=q[head];
	inc(head);
end;

function queue.empty():boolean;
begin exit(head=tail); end;

procedure queue.update();
var i:longint;
begin for i:=head to tail-1 do
            q[i].state:=q[i].state<<2;
end;

var
LAST,CURT:pointer;
map:array[0..10,0..10] of longint;

procedure lemon();
var n,m,i,j,x,ps,len,left,down,ans:longint;
    tmp:pack;
    temp:pointer;
begin fillchar(map,sizeof(map),255);
	readln(n,m); if (n=0)and(m=0) then halt;
	for i:=1 to n do
		for j:=1 to m do
		begin read(x);
			case x of
			0:	map[i,j]:=0;
			1:	map[i,j]:=-1;
			2:	map[i,j]:=1;
			3:	map[i,j]:=2;
			end;
		end;

	CURT^.clear();
	CURT^.insert(0,0);
	for i:=1 to n do
	begin for j:=1 to m do
		begin temp:=LAST; LAST:=CURT; CURT:=temp;
			CURT^.clear();
			while not LAST^.empty() do
			begin tmp:=LAST^.gethead();
				ps:=tmp.state; len:=tmp.len;
				left:=ps>>((j-1)<<1) and 3;
				down:=ps>>(j<<1) and 3;
				if map[i,j]=-1 then
				begin if (left=0)and(down=0) then CURT^.insert(ps,len);
					continue;
				end;
				if (left=0)and(down=0) then
				begin if map[i,j]=0 then
					begin CURT^.insert(ps,len);
                                    if (map[i,j+1]<>-1)and(map[i+1,j]<>-1) then
                                    begin x:=ps+(1<<((j-1)<<1))+(1<<(j<<1));
						      CURT^.insert(x,len+1);
						      x:=ps+((1<<((j-1)<<1))<<1)+((1<<(j<<1))<<1);
						      CURT^.insert(x,len+1);
                                    end;
					 end
					else begin
                                    if map[i+1,j]<>-1 then
						begin x:=ps+map[i,j]*(1<<((j-1)<<1));
                                          CURT^.insert(x,len+1);
                                    end;
						if map[i,j+1]<>-1 then
                                    begin x:=ps+map[i,j]*(1<<(j<<1));
      					      CURT^.insert(x,len+1);
                                    end;
					end;
					continue;
				end;
				if (left<>0)and(down=0) then
				begin if map[i,j]=0 then
					begin if map[i,j+1]<>-1 then
						begin x:=ps-left*(1<<((j-1)<<1))+left*(1<<(j<<1));
							CURT^.insert(x,len+1);
						end;
						if map[i+1,j]<>-1 then CURT^.insert(ps,len+1);
					 end
					else begin
                                    if left<>map[i,j] then continue;
						x:=ps-left*(1<<((j-1)<<1));
						CURT^.insert(x,len+1);
					end;
					continue;
				end;
				if (left=0)and(down<>0) then
				begin if map[i,j]=0 then
					begin if map[i+1,j]<>-1 then
						begin x:=ps-down*(1<<(j<<1))+down*(1<<((j-1)<<1));
							CURT^.insert(x,len+1);
						end;
						if map[i,j+1]<>-1 then CURT^.insert(ps,len+1);
					 end
					else begin
                                    if down<>map[i,j] then continue;
						x:=ps-down*(1<<(j<<1));
						CURT^.insert(x,len+1);
					end;
					continue;
				end;
				if (left<>0)and(down<>0) then
				begin if left<>down then continue;
					if map[i,j]=0 then
					begin x:=ps-left*(1<<((j-1)<<1))-down*(1<<(j<<1));
						CURT^.insert(x,len+1);
					end;
					continue;
				end;
			end;
		end;
		CURT^.update();
	end;

	ans:=maxlongint;
	while not CURT^.empty() do
	begin tmp:=CURT^.gethead();
		if (tmp.state=0)and(tmp.len<ans) then ans:=tmp.len;
	end;
	if ans=maxlongint then writeln(0) else writeln(ans-2);
end;

begin
{$IFNDEF ONLINE_JUDGE}
	assign(input,'3133.in');
	reset(input);
	assign(output,'3133.out');
	rewrite(output);
{$ENDIF}
new(LAST); LAST^.init();
new(CURT); CURT^.init();
while true do lemon();
end.

• orz!!! (15960) peargobble 2011-06-06 18:52:32
• Re:这题太恶心了……插头dp，有8种情况，13种转移，各种特判，写了两个多小时终于a掉了……贴一下代码，给wa的人一个参考…… (32) weihaohaoren 2012-08-21 01:36:36
• gcc版翻译 (2806) Zenomyth 2013-12-20 15:54:46