(C卷,100分)- 找出经过特定点的路径长度（Java & JS & Python）

题目描述

无

输入描述

输入一个字符串，都是以大写字母组成，每个相邻的距离是 1，

第二行输入一个字符串，表示必过的点。

说明每个点可过多次。

输出描述

经过这些必过点的最小距离是多少

用例

题目解析

感觉本题题目描述太简略了，缺少很多关键信息。

• 第一行输入的字符串中是否有重复字母？
• 第二行输入的字符串中是否有重复字母？
• 运动起点在哪？一定是第一行第一个字母吗？（给出的用例无法解答该问题）
• 运动方向变更逻辑是啥？随意变更，还是必须到达终点后折返？（给出的用例无法解答该问题）
• 每个点可过多次，那么是否可以原地走？

因为题目没有这些关键信息，因此这道题目的难度就不确定了。

我是这样考虑的：

• 第一行和第二行都可能出现重复字母
• 运动起点必须从第一行输入的第一个字母开始
• 运动方向可以随意变更
• 允许原地走

这样的话，经过必过点的路径才能多样化，才有最小距离概念。

解题思路如下，首先统计第二行输入的必过点在第一行字符串中的索引位置，需要注意的是必过点可能在第一行中出现多次，我们都要统计到。

下面算法中，我们用points保存必过点信息，idxs保存必过点的索引信息。

接下来，通过dfs求解经过必过点的所有的可能路径。

之后计算这些路径的距离，即相邻两点求差绝对值，然后相加，需要注意的时，我们需要将从起点走到第一个必过点的距离也加入为路径距离。

然后，对所有路径距离进行排序，最小的就是题解。

自测用例：

ANTSEDXQOKPUVGIFWHJLYMCRZB
GUYA 

最小距离44（注意，该最小距离是，必须从第一行输入的首字母出发的最小距离）

ANTSEDXQOKPUVGIFWHUJLYMCRZ
GUYA

 发现有两条路径

绿色路径更短，最小距离42（注意，该最小距离是，必须从第一行输入的首字母出发的最小距离）

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    console.log(getResult(lines[0], lines[1]));
    lines.length = 0;
  }
});

function getResult(all, must) {
  const mustCharIdx = {};
  const mustCharSet = new Set(must);

  for (let i = 0; i < all.length; i++) {
    const c = all[i];
    if (mustCharSet.has(c)) {
      mustCharIdx[c] ? mustCharIdx[c].push(i) : (mustCharIdx[c] = [i]);
    }
  }

  const ans = [Infinity];
  dfs(0, must, mustCharIdx, [], ans);
  return ans[0];
}

function dfs(index, must, mustCharIdx, path, ans) {
  if (path.length == must.length) {
    let dis = path[0]; // 运动起点必须从第一行输入all的第一个字母开始
    // let dis = 0; // 运动起点从all中must第一个字母位置开始

    for (let i = 1; i < path.length; i++) {
      dis += Math.abs(path[i] - path[i - 1]);
    }

    ans[0] = Math.min(ans[0], dis);
    return;
  }

  for (let idx of mustCharIdx[must[index]]) {
    path.push(idx);
    dfs(index + 1, must, mustCharIdx, path, ans);
    path.pop();
  }
}

Java算法源码

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String all = sc.next();
    String must = sc.next();

    System.out.println(getResult(all, must));
  }

  public static int getResult(String all, String must) {
    HashMap<Character, ArrayList<Integer>> mustCharIdx = new HashMap<>();

    HashSet<Character> mustChar = new HashSet<>();
    for (char c : must.toCharArray()) {
      mustChar.add(c);
    }

    for (int i = 0; i < all.length(); i++) {
      char c = all.charAt(i);
      if (mustChar.contains(c)) {
        mustCharIdx.putIfAbsent(c, new ArrayList<>());
        mustCharIdx.get(c).add(i);
      }
    }

    int[] ans = {Integer.MAX_VALUE};
    dfs(0, must, mustCharIdx, new LinkedList<>(), ans);
    return ans[0];
  }

  public static void dfs(
      int index,
      String must,
      HashMap<Character, ArrayList<Integer>> mustCharIdx,
      LinkedList<Integer> path,
      int[] ans) {
    if (path.size() == must.length()) {
      int dis = path.get(0); // 运动起点必须从第一行输入all的第一个字母开始
      // int dis = 0; // 运动起点从all中must第一个字母位置开始
      for (int i = 1; i < path.size(); i++) {
        dis += Math.abs(path.get(i) - path.get(i - 1));
      }
      ans[0] = Math.min(ans[0], dis);
      return;
    }

    for (Integer idx : mustCharIdx.get(must.charAt(index))) {
      path.add(idx);
      dfs(index + 1, must, mustCharIdx, path, ans);
      path.removeLast();
    }
  }
}

Python算法源码

import sys

# 输入获取
all = input()
must = input()


def dfs(index, must, mustCharIdx, path, ans):
    if len(path) == len(must):
        dis = path[0]  # 运动起点必须从第一行输入all的第一个字母开始
        # dis = 0  # 运动起点从all中must第一个字母位置开始

        for i in range(1, len(path)):
            dis += abs(path[i] - path[i - 1])

        ans[0] = min(ans[0], dis)
        return

    for idx in mustCharIdx[must[index]]:
        path.append(idx)
        dfs(index + 1, must, mustCharIdx, path, ans)
        path.pop()


def getResult(all, must):
    mustCharIdx = {}

    mustChar = set(must)

    for i in range(len(all)):
        c = all[i]

        if c in mustChar:
            if mustCharIdx.get(c) is None:
                mustCharIdx[c] = []
            mustCharIdx[c].append(i)

    ans = [sys.maxsize]
    dfs(0, must, mustCharIdx, [], ans)
    return ans[0]


print(getResult(all, must))