关注
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static int[][] maze = {
{-1, -1, -1, -1, -1, -1, -1},
{-1, 0, 2, 10, 5, 3, -1},
{-1, -1, 0, 12, -1, -1, 10},
{-1, -1, -1, 0, -1, 7, -1},
{-1, 2, -1, -1, 0, 2, -1},
{-1, 4, -1, -1, 1, 0, -1},
{-1, 3, -1, 1, -1, 2, 0}};
public static int minDis = Integer.MAX_VALUE;
public static ArrayList<Integer> result = null;
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int X = 0, Y = 0;
while (scanner.hasNext()) {
X = scanner.nextInt();
Y = scanner.nextInt();
Stack<Integer> path = new Stack<Integer>();
boolean[] visited = new boolean[7];
main.initVisited(visited);
visited[5] = true;
path.push(5);
main.dfs(path, visited, 5, 0, X, Y);
if (result == null) {
System.out.println(1000);
System.out.println(new ArrayList<Integer>());
} else {
System.out.println(minDis);
System.out.println(result);
}
minDis = Integer.MAX_VALUE;
result = null;
}
}
private void dfs(Stack<Integer> path, boolean[] visited, int currentCity, int distance, int target, int forbidden) {
if (currentCity == target) {
if (distance < minDis) {
minDis = distance;
result = new ArrayList<Integer>();
for (int i = 0; i < path.size(); i++) {
result.add(path.get(i));
}
}
return;
}
for (int i = 1; i <= 6; i++) {
if (visited[i]) {
continue;
}
if (maze[currentCity][i] == -1) {
continue;
}
if (currentCity == forbidden || i == forbidden) {
continue;
}
path.push(i);
visited[i] = true;
dfs(path, visited, i, distance + maze[currentCity][i], target, forbidden);
visited[i] = false;
path.pop();
}
}
private void initVisited(boolean[] visited) {
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}
}
}
查看原帖
点赞 1
相关推荐
查看23道真题和解析
点赞 评论 收藏
分享
06-11 12:18
东南大学 电子信息类 点赞 评论 收藏
分享
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
1363614次浏览 18989人参与
# 非技术岗薪资爆料 #
56060次浏览 743人参与
# 不去互联网可以去金融科技 #
49321次浏览 509人参与
# 和牛牛一起刷题打卡 #
50162次浏览 4003人参与
# 如果可以选,你最想去哪家公司 #
567074次浏览 9466人参与
# 互联网公司评价 #
108942次浏览 1407人参与
# 极具前瞻性,现代汽车编程题 #
11730次浏览 219人参与
# 产品每日一题 #
3564次浏览 155人参与
# 现在还是0offer,延毕还是备考 #
435237次浏览 4991人参与
# 我的上岸简历长这样 #
229858次浏览 4539人参与
# 运营人的第一份offer应该如何选 #
42430次浏览 698人参与
# 0offer是寒冬太冷还是我太菜 #
477637次浏览 5290人参与
# 你会选择考研还是直接就业 #
91743次浏览 1069人参与
# 实习必须要去大厂吗? #
27573次浏览 477人参与
# 想实习转正,又想准备秋招,我该怎么办 #
181788次浏览 2021人参与
# 来聊聊你目前的求职进展 #
233261次浏览 2950人参与
# 安利/避雷我的岗位 #
186645次浏览 3259人参与
# 春招你拿到offer了吗 #
422945次浏览 5974人参与
# 如果可以选,你最想从事什么工作 #
224251次浏览 3439人参与
# 硬件兄弟们 甩出你的华为奖状 #
38995次浏览 228人参与
# 简历中的项目经历要怎么写 #
519191次浏览 9511人参与
# 我想象的工作vs实际工作 #
119648次浏览 1838人参与