GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Saturday 6 August 2022

[Solution] Traveling Salesman Problem Codeforces Solution



A. Traveling Salesman Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are living on an infinite plane with the Cartesian coordinate system on it. In one move you can go to any of the four adjacent points (left, right, up, down).

More formally, if you are standing at the point (x,y), you can:

  • go left, and move to (x1,y), or
  • go right, and move to (x+1,y), or
  • go up, and move to (x,y+1), or
  • go down, and move to (x,y1).

There are n boxes on this plane. The i-th box has coordinates (xi,yi). It is guaranteed that the boxes are either on the x-axis or the y-axis. That is, either xi=0 or yi=0.

You can collect a box if you and the box are at the same point. Find the minimum number of moves you have to perform to collect all of these boxes if you

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 have to start and finish at the point (0,0).

Input

The first line contains a single integer t (1t100) — the number of test cases.

The first line of each test case contains a single integer n (1n100) — the number of boxes.

The i-th line of the following n lines contains two integers xi and yi (100xi,yi100) — the coordinate of the i-th box. It is guaranteed that either xi=0 or yi=0.

Do note that the sum of n over all test cases is not bounded.

Output

For each test case output a single integer — the minimum number of moves required.

No comments:

Post a Comment