Traveling Salesman 的做法是什么

Question

Problem Description
Long before the days of international trade treaties, a salesman would need to pay taxes at every border crossed. So your task is to find the minimum number of borders that need to be crossed when traveling between two countries. We model the surface of Earth as a set of polygons in three dimensions forming a closed convex 3D shape, where each polygon corresponds to one country. You are not allowed to cross at points where more than two countries meet.

Input
Each test case consists of a line containing c, the number of countries (4 ≤ c ≤ 6000), followed by c lines containing the integers n x1 y1 z1 … xn yn zn, describing (in order) the n corners of a closed polygon (3 ≤ n ≤ 20). Then follows a line with one integer m (0 < m ≤ 50), and then m lines with queries ca cb, where ca and cb are country numbers (starting with 1). No point will be on the line between two connected points, and -106 ≤ x, y, z ≤ 106 for all points. No two non-adjacent edges of a country share a common point. The input is terminated by a case where c = 0, which should not be processed.

Output
For each query, output the number of borders you must cross to go from ca to cb.

Sample Input
6
4 0 0 0 0 0 1 0 1 1 0 1 0
4 1 0 0 1 0 1 1 1 1 1 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 1 0 1 1 0 1 1 1 0 1 1
4 0 0 0 0 1 0 1 1 0 1 0 0
4 0 0 1 0 1 1 1 1 1 1 0 1
2
1 2
1 3
0

Sample Output
2
1

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 读取数据
input <- readLines()

c <- as.integer(input[1])
polygons <- matrix(NA, c(c, 8*c))
for(i in 2:(c+1)) {
    temp <- as.numeric(gsub("[^0-9]", "", input[i]))
    polygons[i-2] <- temp[1:8]
}

m <- as.integer(input[c+2])
queries <- matrix(NA, c(m, 2))

# 计算边的数量
border_count <- function(x) sum(duplicated(x))

# 遍历每个查询点
for(i in 1:m) {
    query <- as.integer(input[c+i+3])
    
    # 确定起始和结束的国家
    start_country <- query %/% c + 1
    end_country <- (query - start_country) %% c + 1
    
    # 计算边的数量
    border_count(start_country) <- border_count(start_country) + border_count(end_country)
    border_count(end_country) <- border_count(end_country) + border_count(start_country)
    
    # 输出结果
    print(border_count(query))
}

这段代码使用了 R 进行编程。首先读取输入数据，并将它们转换为矩阵形式，以便于计算。然后遍历所有查询点，并根据起始和结束国家的位置来计算边的数量，最后输出这些边的数量。