好久沒寫Dfs了，拿來練手。

WA了一次，沒有判斷中間的情況……

解法：先用Floyd傳遞閉包處理哪些點一定要在一起、哪些點一定不能在一起，六重循環(huán)。

然后深搜，res[i][j]表示1,i這個物品在j這一行的匹配物品列編號。

沒有最優(yōu)性剪枝，只有一堆可能性剪枝：

(1)對于和(1,i)這個點關(guān)系為“一定在一起”的點(j,k)，一定要將res[i,j]設置為k。

(2)即將搜索res[i][j]為k的情況是否可能，那么條件就要是(j,k)這個點與(1,i)點的關(guān)系不是“不可能在一起”，而且(j,k)這個點與所有已經(jīng)和(1,i)點匹配的點的關(guān)系不是“不可能在一起”。

參考代碼：

program poj1683;//By_Thispoet const maxn=10; varx1,y1,x2,y2 :longint;i,j,m,n,p,q,test :longint;map :array[0..maxn,0..maxn,0..maxn,0..maxn]of integer;res :array[0..maxn,0..maxn]of integer;v :array[0..maxn,0..maxn]of boolean;ch :array[0..maxn,0..maxn]of char;c,cc :char;flag :boolean;procedure printf(); beginfor i:=1 to m do beginfor j:=1 to n do write(ch[j,res[i,j]]);writeln;end;writeln; end;procedure dfs(code,pos:longint);var i,j,k:longint;beginif code=n+1 then beginprintf();flag:=true;exit;end;if res[pos,code]<>-1 then beginif pos+1<=m then dfs(code,pos+1) else dfs(code+1,1);exit;end;if flag then exit;for i:=1 to m do if (not v[code][i])and(map[1,pos,code,i]<>2) then beginfor j:=code+1 to n do for k:=1 to m do if (map[code,i,j,k]=1)and(res[pos,j]<>-1)then beginflag:=true;break;end;for j:=1 to code-1 do if map[code,i,j,res[pos,j]]=2 then beginflag:=true;break;end;if flag then begin flag:=false; continue; end;v[code][i]:=true;res[pos,code]:=i;for j:=code+1 to n do for k:=1 to m do if (map[code,i,j,k]=1) then beginres[pos,j]:=k;v[j,k]:=true;break;end;if pos+1<=m then dfs(code,pos+1) else dfs(code+1,1);if flag then exit;for j:=code+1 to n do for k:=1 to m do if map[code,i,j,k]=1 then beginres[pos,j]:=-1;v[j,k]:=false;break;end;v[code][i]:=false;res[pos,code]:=-1;end; end;beginreadln(test);while test>0 do beginreadln(n,m);filldword(map,sizeof(map)shr 2,0);fillchar(res,sizeof(res),255);for i:=1 to n do beginfor j:=1 to m do read(ch[i][j]);readln;end;flag:=false;readln(x1,y1,cc,c,cc,x2,y2);while not (x1=0) do beginif c='R' then beginmap[x1,y1,x2,y2]:=1;map[x2,y2,x1,y1]:=1;end else beginmap[x1,y1,x2,y2]:=2;map[x2,y2,x1,y1]:=2;end;readln(x1,y1,cc,c,cc,x2,y2);end;for p:=1 to n do for q:=1 to m dofor x1:=1 to n do for y1:=1 to m dofor x2:=1 to n do for y2:=1 to m dobeginif (map[x1,y1,p,q]=1)and(map[x2,y2,p,q]=2) then map[x1,y1,x2,y2]:=2;if (map[x1,y1,p,q]=2)and(map[x2,y2,p,q]=1) then map[x1,y1,x2,y2]:=2;if (map[x1,y1,p,q]=1)and(map[x2,y2,p,q]=1) then map[x1,y1,x2,y2]:=1;end;fillchar(v,sizeof(v),0);for i:=1 to m do res[i,1]:=i;for i:=1 to m do for p:=2 to n do for q:=1 to m doif map[1,i,p,q]=1 then begin res[i,p]:=q; v[p,q]:=true; end;dfs(1,1);dec(test);end; end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/Thispoet/archive/2011/11/01/2232041.html

總結(jié)

以上是生活随笔為你收集整理的POJ1683 Puzzlestan ——Floyd传递闭包+Dfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。