- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试使用 C 中的 BackTracking 解决以下问题,但我不知道如何从这里继续...
问题是:
克里斯计划去一个有 N 个城市的国家旅行。他将得到一个矩阵 NxN 的帮助,其中单元格 (I,J) 代表从城市 I 到城市 J 的道路长度。与从城市 B 到城市 A 的道路相比,从城市 A 到城市 B 的道路长度并不相同。从同一源城市返回(直接)的道路为 0。克里斯注意到从 A 到 B 的最短路线并不总是连接两个城市的直接道路。您需要帮助克里斯找到最短路径。编写一个函数,在给定存储道路长度值的 NxN 矩阵的情况下检查最短 map 。注:N定义为4。
示例:
如果给定以下矩阵,从 0 到 1 的最短路径是先到城市 0,然后到 3,然后到 1:
0 5 2 2
1 0 1 1
1 2 0 1
1 1 2 0
她是我的代码:
int ShortestPath (int SourceCity, int DestinationCity, int Distance [][N], bool Chosen[][N])
{
int Path=0;
if (SourceCity==DestinationCity)
{
Distance[SourceCity][DestinationCity]=true;
return 0;
}
for (int i=0;i<N;i++)
{
for (int j=0;j<N;j++)
{
Path += Distance[i][j];
if (!Chosen[i][j])
{
Chosen[i][j] = true;
ShortestPath(i, DestinationCity, Distance, Chosen);
}
}
}
if (Path>=Distance[SourceCity][DestinationCity])
{
Chosen[SourceCity,DestinationCity]=false;
return Distance[SourceCity][DestinationCity];
}
}
注意:选择的矩阵表示我是否选择了特定道路(其初始值均为 false)
最佳答案
这是一个建议的解决方案。它是寻找最短路径的 Dijkstra 算法的实现。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
// number of nodes
#define N 4
// distance matrix from i to j for d[i][j]
int d[N][N] = {
{0, 5, 2, 2},
{1, 0, 1, 1},
{1, 2, 0, 1},
{1, 1, 2, 0},
};
// shortestPath stores in path the shortest path from start node to
// final node using the distance matrix d. It returns the number of
// nodes in the path.
int shortestPath(int d[N][N], int start, int final, int path[N]){
// node previous to node i
int prev[N];
// initialize distance from node i to start as infinite
int dist[N];
for (int i = 0; i < N; i++)
dist[i] = INT_MAX;
dist[start] = 0;
// initialize list of nodes done
bool done[N];
for (int i = 0; i < N; i++)
done[i] = false;
int nDone = 0;
// while we haven’t done all nodes
while (nDone < N) {
// find not yet done node with minimal distance to start node
int minDist = INT_MAX;
int n; // node with minimum distance
for (int i = 0; i < N; i++)
if (!done[i] && dist[i] < minDist)
minDist = dist[n = i];
done[n] = true;
nDone++;
// we can stop when final node is done
if (n == final)
break;
// for every node j...
for (int j = 0; j < N; j++) {
// if node j is not yet done,
// and distance from start to j through n is smaller to known
if (!done[j] && dist[j] > dist[n] + d[n][j]) {
// set new shortest distance
dist[j] = dist[n] + d[n][j];
// set node n as previous to node j
prev[j] = n;
}
}
}
// get path [start, ..., final]
int j = N;
for (int i = final; i != start; i = prev[i])
path[--j] = i;
path[--j] = start;
if (j == 0)
return N;
int n = N-j;
for (int i = 0; i < n; i++, j++)
path[i] = path[j];
return n;
}
int main() {
int path[N];
int n = shortestPath(d, 0, 1, path);
printf("path: %d", path[0]);
for (int i = 1; i < n; i++)
printf("->%d", path[i]);
printf("\n");
return 0;
}
输出
path: 0->3->1
关于c - BackTracking 功能未按预期工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59689774/
我找到了 this excellent question and answer它以 x/y(加上 center x/y 和 degrees/radians)开始并计算旋转- 到 x'/y'。这个计算很
全部: 我已经创建了一个 Windows 窗体和一个按钮。在另一个线程中,我试图更改按钮的文本,但它崩溃了;但是如果我尝试更改按钮的颜色,它肯定会成功。我认为如果您更改任何 Windows 窗体控件属
本网站的另一个问题已证实,C 中没有缩写的字面后缀,并且可以执行以下操作: short Number = (short)1; 但是转换它和不这样做有什么区别: short Number = 1; 您使
我有下表: ID (int) EMAIL (varchar(50)) CAMPAIGNID (int) isSubscribe (bit) isActionByUser (bit) 此表存储了用户对事
也就是说,无需触发Javascript事件即可改变的属性,如何保留我手动选中或取消选中的复选框的状态,然后复制到另一个地方? 运行下面的代码片段并选中或取消选中其中的一些,然后点击“复制”: $('#
我在网上找到的所有关于递增指针导致段错误的示例都涉及指针的取消引用 - 如果我只想递增它(例如在 for 循环的末尾)并且我不在乎它是否最终进入无效内存,因为我不会再使用它。例如,在这个程序中,每次迭
我有一个 Spring MVC REST 服务,它使用 XStream 将消息与 XML 相互转换。 有什么方法可以将请求和响应中的 xml(即正文)打印到普通的 log4j 记录器? 在 Contr
做我的任务有一个很大的挑战,那就是做相互依赖的任务我在这张照片中说的。假设我们有两个任务 A 和 B,执行子任务 A1、A2 和 B1、B2,假设任务 B 依赖于 A。 要理想地执行任务 B,您应该执
通过阅读该网站上的几个答案,我了解到 CoInitialize(Ex) should be called by the creator of a thread 。然后,在该线程中运行的任何代码都可以使
这个问题已经困扰我一段时间了。我以前从未真正使用过 ListViews,也没有使用过 FirebaseListAdapters。我想做的就是通过显示 id 和用户位置来启动列表的基础,但由于某种原因,
我很难解释这两个(看似简单)句子的含义: “受检异常由编译器在编译时检查” 这是什么意思?编译器检查是否捕获了所有已检查的异常(在代码中抛出)? “未经检查的异常在运行时检查,而不是编译时” 这句话中
我有一个包含排除子字符串的文本文件,我想迭代该文件以检查并返回不带排除子字符串的输入项。 这里我使用 python 2.4,因此下面的代码可以实现此目的,因为 with open 和 any 不起作用
Spring 的缓存框架能否了解请求上下文的身份验证状态,或者更容易推出自己的缓存解决方案? 最佳答案 尽管我发现这个用例 super 奇怪,但您可以为几乎任何与 SpEL 配合使用的内容设置缓存条件
我有以下函数模板: template HeldAs* duplicate(MostDerived *original, HeldAs *held) { // error checking omi
如果我的应用程序具有设备管理员/设备所有者权限(未获得 root 权限),我如何才能从我的应用程序中终止(或阻止启动)另一个应用程序? 最佳答案 设备所有者可以阻止应用程序: DevicePolicy
非常简单的问题,但我似乎无法让它正常工作。 我有一个组件,其中有一些 XSLT(用于导航)。它通过 XSLT TBB 使用 XSLT Mediator 发布。 发布后
我正在将一个对象拖动到一个可拖放的对象内,该对象也是可拖动的。放置对象后,它会嵌套在可放置对象内。同样,如果我将对象拖到可放置的外部,它就不再嵌套。 但是,如果我经常拖入和拖出可放置对象,则可拖动对象
我正在尝试为按钮和弹出窗口等多个指令实现“取消选择”功能。也就是说,我希望当用户单击不属于指令模板一部分的元素时触发我的函数。目前,我正在使用以下 JQuery 代码: $('body').click
我从 this question 得到了下面的代码,该脚本用于在 Google tasks 上更改 iframe[src="about:blank"] 内的 CSS使用 Chrome 扩展 Tempe
我有一些 @Mock 对象,但没有指定在该对象上调用方法的返回值。该方法返回 int (不是 Integer)。我很惊讶地发现 Mockito 没有抛出 NPE 并返回 0。这是预期的行为吗? 例如:
我是一名优秀的程序员,十分优秀!