C++实现返回将箱子推动到目标位置的箱子最小推动次数。箱子BFS，人DFS实现。算法具体要求如下：
推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 n * m 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：
玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 '.' 表示，意味着可以自由行走。
墙用字符 '#' 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。
2021-08-03 09:27:06
5KB
1
/*
* （有向）图的深度优先遍历算法模板
*/
package dsa;
public abstract class DFS extends GraphTraverse {
//变量
protected static int clock = 0;//遍历过程中使用的计时钟
//构造方法
public DFS(Graph g) { super(g); }
//深度优先遍历算法
protected Object traverse(Vertex v, Object info) {//从顶点v出发，做深度优先查找
if (UNDISCOVERED != v.getStatus()) return null;//跳过已访问过的顶点（针对非连通图）
v.setDStamp(clock++); v.setStatus(DISCOVERED); visit(v, info);//访问当前顶点
for (Iterator it = v.outEdges(); it.hasNext();) {//检查与顶点v
Edge e = (Edge)it.getNext();//通过边e = (v, u)
Vertex u = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u
switch (u.getStatus()) {//根据u当前的不同状态，分别做相应处理
case UNDISCOVERED ://若u尚未被发现，则
e.setType(TREE);//e被归类为“树边”
traverse(u, info);//从u出发，继续做深度优先查找
break;
case DISCOVERED ://若u已经被发现，但对其访问尚未结束，则
e.setType(BACKWARD);//将e归类为“后向跨边”
break;
default ://VISITED，即对u的访问已经结束
if (u.getDStamp() < v.getDStamp())//若相对于v，u被发现得更早，则
e.setType(CROSS);//将e归类为“横跨边”
else//否则
e.setType(FORWARD);//将e归类为“前向跨边”
break;
}
}//至此，v的所有邻居都已访问结束，故
v.setFStamp(clock++); v.setStatus(VISITED);//将v标记为VISITED
return null;//然后回溯
}
}
2021-07-30 00:56:24
3KB
1
处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的 时间尽可能地短，出门旅游的旅客则期望旅费尽可能省，而老年旅客则要求中转次数最少。 编织一个全国城市间的交通资讯程序，为旅客提供两种或三种最优决策的交通咨询。亮点是对最小中转次数的处理，因为火车一趟车次会有很多个中间站，不能和飞机一样处理。
2021-07-06 11:28:32
983KB
1
本资源包含“基于蛮力法（DFS）解决TSP问题”的相关代码以及TSP的城市数据。 本资源包含“基于蛮力法（DFS）解决TSP问题”的相关代码以及TSP的城市数据。
2021-06-21 14:35:57
7KB
1