Resource constraints

Time limit: 1.0s   Memory limit: 256.0MB

Problem description

zsyzgu is A weak dish. Nevertheless, he participated in the agent series. The problem of the agent series is simplified as follows. There is A monkey and some mining points. They know their coordinates on the plane. The monkey has to pass through these mining points at least once. Suppose that the number of steps for the monkey to walk from point A to point B is the Manhattan distance between the two points (i.e. | A.x-b.x + | A.y-b.y), ask the monkey the minimum number of steps required to pass through these mines at least once.
Many players in the series used a greedy strategy, that is, they went to the nearest unexplored mine every time. But zsyzgu's idea is to search, which is why he can get rid of the bottom fate and get the commemorative version of T-shirt.

Input format

The two numbers in the first line represent the coordinates of the monkey;
A number n in the second line represents the number of ore occurrences;
The next n lines, two numbers per line, represent the coordinates of each ore point.

Output format

One number per line represents the minimum number of steps.

sample input

0 0
4
0 1
0 2
0 3
0 -2

sample output

7

Data scale and agreement

For 100% data: 1 < = n < = 10, the abscissa and ordinate are integers, and its absolute value is < = 10000.

Problem solving ideas:

It is suggested in the question to use search, and the number of mining points given in the question is very small, so search all mining points directly, arrange the number of mining points, and find the minimum number of steps on the basis of good arrangement.

Since each point is given in the form of coordinates, the coordinates can be encapsulated into classes to simplify the processing of data.

Full permutation problem:

Total permutation problemhttps://blog.csdn.net/weixin_48898946/article/details/121589155

java code:

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int x = Integer.parseInt(split[0]);
		int y = Integer.parseInt(split[1]);
		Loca1179 start = new Loca1179(x, y);//Starting point coordinates
		int n = Integer.parseInt(br.readLine());
		Loca1179 []couple = new Loca1179[n + 1];//Number of ore point coordinates required to pass
		for(int i = 1; i <= n; i++) {
			split = br.readLine().split(" ");
			x = Integer.parseInt(split[0]);
			y = Integer.parseInt(split[1]);
			couple[i] = new Loca1179(x, y);
		}
		Temp1179 obj = new Temp1179(start, n, couple);
		obj.dfs(1);
		System.out.println(obj.ans);
	}
}

class Temp1179{
	Loca1179 start;//Starting coordinates
	int n;//Points to be passed
	Loca1179 []couple;//Coordinates of ore occurrence
	boolean []vis;//Indicates whether a mine has been visited
	List<Integer> list = new ArrayList<>();//Sequence of deposit passing in real time
	int ans = Integer.MAX_VALUE;//The top of the start path is infinity
	int sum = 0;
	
	public Temp1179(Loca1179 start, int n, Loca1179[] couple) {
		this.start = start;
		this.n = n;
		this.couple = couple;
		vis = new boolean[n + 1];
	}
	
	public void dfs(int step) {
		if(step > n) {
			compare();//Compare the cumulative distance required each time
			return;
		}
		for(int i = 1; i <= n; i++) {
			if(!vis[i]) {
				vis[i] = true;
				list.add(i);
				dfs(step + 1);
				vis[i] = false;//to flash back
				list.remove(list.size() - 1);
			}
		}
	}
	
	public void compare() {
		sum = 0;
		sum += Math.abs(start.x - couple[list.get(0)].x) + Math.abs(start.y - couple[list.get(0)].y);//Starting point to the first occurrence
		for(int i = 1; i < list.size(); i++) {
			sum += Math.abs(couple[list.get(i)].x - couple[list.get(i - 1)].x) + Math.abs(couple[list.get(i)].y - couple[list.get(i - 1)].y);
		}
		if(sum < ans) {
			ans = sum;
		}
	}
}

class Loca1179{//Coordinate class
	int x;
	int y;
	
	public Loca1179(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

Submit screenshot: