P2537 [AHOI2005] Crossing Magnetic Fields

An exploration robot is searching for a peculiar ore on planet Samuel, but it has become trapped in a mysterious magnetic field region and cannot move. The exploration station immediately scanned the area and drew a planar map of the magnetic field distribution. There are $N$ magnetic fields in this region. Each magnetic field is a square whose sides are parallel to the coordinate axes. For example, in the figure below, there are $3$ magnetic fields. The white dot is the robot’s position, and the black dot is the ore’s position:  After analyzing the map, scientists further found that these magnetic fields are squares of various sizes. They may intersect or even overlap, but their edges never coincide, and their vertices never coincide. For example, the following two cases will not occur:  Scientists activated a magnetic shield for the exploration robot so that it can move freely through the magnetic fields. Initially, neither the robot nor any ore lies on any magnetic field edge. Due to technical limitations, during traversal the robot can only move horizontally or vertically, and it cannot move along the edges of magnetic fields. Because the magnetic shield’s energy is limited, the scientists hope the robot will cross as few magnetic field edges as possible to collect the ore. In the example above, the robot needs to cross edges at least twice. Now, please write a program to help the scientists design the robot’s route and compute the minimum number of magnetic field edges the robot must cross.

The first line contains an integer $N$, meaning there are $N$ magnetic fields ($1 < N < 100$). Then follow $N$ lines, each containing three integers $X, Y, C$ ($0 < X, Y, C < 10000$), indicating a magnetic field whose lower-left corner is $(X, Y)$ and whose side length is $C$. The next line contains four integers $SX, SY, TX, TY$, indicating that the robot’s initial coordinate is $(SX, SY)$ and the ore’s coordinate is $(TX, TY)$ (where $1 < SX, SY, TX, TY < 10000$).

Output a single integer on one line, the minimum number of magnetic field edges the robot needs to cross.

Translated by ChatGPT 5