大型门户网站源码,爱战网关键词挖掘,最主流的网页制作软件,天河做网站好久没写Dfs了#xff0c;拿来练手。 WA了一次#xff0c;没有判断中间的情况…… 解法#xff1a;先用Floyd传递闭包处理哪些点一定要在一起、哪些点一定不能在一起#xff0c;六重循环。 然后深搜#xff0c;res[i][j]表示1,i这个物品在j这一行的匹配物品列编号。 没有最…好久没写Dfs了拿来练手。 WA了一次没有判断中间的情况…… 解法先用Floyd传递闭包处理哪些点一定要在一起、哪些点一定不能在一起六重循环。 然后深搜res[i][j]表示1,i这个物品在j这一行的匹配物品列编号。 没有最优性剪枝只有一堆可能性剪枝 (1)对于和(1,i)这个点关系为“一定在一起”的点(j,k)一定要将res[i,j]设置为k。 (2)即将搜索res[i][j]为k的情况是否可能那么条件就要是(j,k)这个点与(1,i)点的关系不是“不可能在一起”而且(j,k)这个点与所有已经和(1,i)点匹配的点的关系不是“不可能在一起”。 参考代码 program poj1683;//By_Thispoet
const maxn10;
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 coden1 then beginprintf();flag:true;exit;end;if res[pos,code]-1 then beginif pos1m then dfs(code,pos1) else dfs(code1,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:code1 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:code1 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 pos1m then dfs(code,pos1) else dfs(code1,1);if flag then exit;for j:code1 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 test0 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 (x10) do beginif cR 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.转载于:https://www.cnblogs.com/Thispoet/archive/2011/11/01/2232041.html
