深搜(一)

程序设计与算法(二)郭炜信息科学技术学院1深度优先搜索入门：城堡问题23在图上寻找路径123456789A在图上如何寻找从1到8的路径?一种策略：只要能发现没走过的点，就走到它。有多个点可走就随便挑一个，如果无路可走就回退，再看有没有没走过的点可走4在图上寻找路径123456789A在图上如何寻找从1到8的路径?运气最好：1-2-4-85在图上寻找路径123456789A在图上如何寻找从1到8的路径?运气最好：1-2-4-8运气稍差：1-2-4-5-6-86在图上寻找路径123456789A在图上如何寻找从1到8的路径?运气最好：1-2-4-8运气稍差：1-2-4-5-6-8运气坏：1-3-7-9=7-A=7=3-5-6-8（双线箭头表示回退）7在图上寻找路径123456789不连通的图，无法从节点1走到节点8。完整的尝试过程可能如下：1-2-4-3-7=3=4=2-9=2=1结论：不存在从1到8的路径得出这个结论之前，一定会把从1出发能走到的点全部都走过。8在图上寻找路径123456789不连通的图，无法从节点1走到节点8。完整的尝试过程可能如下：1-2-4-3-7=3=4=2-9=2=1结论：不存在从1到8的路径得出这个结论之前，一定会把从1出发能走到的点全部都走过。9深度优先搜索(Depth-First-Search)从起点出发，走过的点要做标记，发现有没走过的点，就随意挑一个往前走，走不了就回退，此种路径搜索策略就称为“深度优先搜索”，简称“深搜”。其实称为“远度优先搜索”更容易理解些。因为这种策略能往前走一步就往前走一步，总是试图走得更远。所谓远近(或深度），就是以距离起点的步数来衡量的。10判断从V出发是否能走到终点：boolDfs(V){if(V为终点）returntrue;if(V为旧点)returnfalse;将V标记为旧点;对和V相邻的每个节点U{if(Dfs(U)==true)returntrue;}returnfalse;}在图上寻找路径11intmain(){将所有点都标记为新点;起点=1终点=8coutDfs(起点）;}在图上寻找路径12判断从V出发是否能走到终点,如果能，要记录路径：Nodepath[MAX_LEN];//MAX_LEN取节点总数即可intdepth;boolDfs(V){if(V为终点）{path[depth]=V;returntrue;}if(V为旧点)returnfalse;将V标记为旧点;path[depth]=V;++depth;在图上寻找路径13对和V相邻的每个节点U{if(Dfs(U)==true)returntrue;}--depth;returnfalse;}intmain(){将所有点都标记为新点;depth=0;if(Dfs(起点））{for(inti=0;i=depth;++i)coutpath[i]endl;}}在图上寻找路径14在图上寻找路径123456789A1-3-7-9=7-A=7=3-5-6-8path:1,3,5,6,815Dfs(V){if(V是旧点)return;将V标记为旧点;对和V相邻的每个点U{Dfs(U);}}intmain(){将所有点都标记为新点;while(在图中能找到新点k)Dfs(k);}遍历图上所有节点16用一个二维数组G存放图，G[i][j]表示节点i和节点j之间边的情况(如有无边，边方向，权值大小等)。遍历复杂度：O(n2)n为节点数目图的表示方法--邻接表17每个节点V对应一个一维数组(vector)，里面存放从V连出去的边，边的信息包括另一顶点，还可能包含边权值等。图的表示方法--邻接表231491472368583561234567832遍历复杂度：O(n+e)n为节点数目，e为边数目2918例题：百练2815城堡问题右图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。19输入输出输入程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。输出城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。20样例输入47116116310679613515511012713751311108101213样例输出5921解题思路把方块看作是节点，相邻两个方块之间如果没有墙，则在方块之间连一条边，这样城堡就能转换成一个图。求房间个数，实际上就是在求图中有多少个极大连通子图。一个连通子图，往里头加任何一个图里的其他点，就会变得不连通，那么这个连通子图就是极大连通子图。（如：(8,5,6))22解题思路对每一个房间，深度优先搜索，从而给这个房间能够到达的所有位置染色。最后统计一共用了几种颜色，以及每种颜色的数量。比如1122333111234311153531555553从而一共有5个房间，最大的房间（1）占据9个格子23#includeiostream#includestack#includecstringusingnamespacestd;intR,C;//行列数introoms[60][60];intcolor[60][60];//方块是否染色过的标记intmaxRoomArea=0,roomNum=0;introomArea;voidDfs(inti,intk){if(color[i][k])return;++roomArea;color[i][k]=roomNum;if((rooms[i][k]&1)==0)Dfs(i,k-1);//向西走if((rooms[i][k]&2)==0)Dfs(i-1,k);//向北if((rooms[i][k]&4)==0)Dfs(i,k+1);//向东if((rooms[i][k]&8)==0)Dfs(i+1,k);//向南}24intmain(){cinRC;for(inti=1;i=R;++i)for(intk=1;k=C;++k)cinrooms[i][k];memset(color,0,sizeof(color));for(inti=1;i=R;++i)for(intk=1;k=C;++k){if(!color[i][k]){++roomNum;roomArea=0;Dfs(i,k);maxRoomArea=max(roomArea,maxRoomArea);}}coutroomNumendl;coutmaxRoomAreaendl;}复杂度：O(R*C)25例题：百练4982踩方格有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a.每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b.走过的格子立即塌陷无法再走第二次；c.只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步(n=20)，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。26例题：百练4982踩方格思路：递归从(i,j)出发，走n步的方案数，等于以下三项之和：从(i+1,j)出发，走n-1步的方案数。前提：(i+1,j)还没走过从(i,j+1)出发，走n-1步的方案数。前提：(i,j+1)还没走过从(i,j-1)出发，走n-1步的方案数。前提：(i,j-1)还没走过27#includeiostream#includecstringusingnamespacestd;intvisited[30][50];intways(inti,intj,intn){if(n==0)return1;visited[i][j]=1;intnum=0;if(!visited[i][j-1])num+=ways(i,j-1,n-1);if(!visited[i][j+1])num+=ways(i,j+1,n-1);if(!visited[i+1][j])num+=ways(i+1,j,n-1);visited[i][j]=0;returnnum;}28#includeiostream#includecstringusingnamespacestd;intvisited[30][50];intways(inti,intj,intn){if(n==0)return1;visited[i][j]=1;intnum=0;if(!visited[i][j-1])num+=ways(i,j-1,n-1);if(!visited[i][j+1])num+=ways(i,j+1,n-1);if(!visited[i+1][j])num+=ways(i+1,j,n-1);visited[i][j]=0;returnnum;}i-1,j,n+1i,j,ni-1,j-1,ni-1,j+1,n29intmain(){intn;cinn;memset(visited,0,sizeof(visited));coutways(0,25,n)endl;return0;}