WA in the Problem PHCUL

Consider this test case:
1
0 0
2 2 1
1 0 1 1
2 2 4 3
3 3

Here we have starting point (x,y) as (0,0)
Points in N as (1,0) and (1,1)
Points in M as (2,2) and (4,3)
Points in K as (3,3)

Let us consider the path as start -> N -> M -> K (for now)
Step 1: Distance of points in N from (0,0)
i) point (1,0) lies at a distance of 1.00
ii) point (1,1) lies at a distance of 1.41

Your approach selects point (i). Lets go with it
Step 2: Distance of points in M from (1,0)
i) point (2,2) lies at a distance of 2.23
ii) point (4,3) lies at a distance of 4.24

Your approach selects point (i). Lets go with it
Step 3: Distance of points in K from (2,2)
i) point (3,3) lies at a distance of 1.41

Path selected: (0,0) -> (1,0) -> (2,2) -> (3,3)
Total distance=1.00+3.23+1.41=7.47
This is your output. However there exists a better path with minimum distance.

In Step 1, if you select point (ii) then,
Step A: Distance of points in M from (1,1)
a)point (2,2) lies at a distance of 1.41
b) point (4,3) lies at a distance of 3.61

If we select point (a), then
Step B: Distance of points in K from (2,2)
a) point (3,3) lies at a distance of 1.41

Path selected: (0,0) -> (1,1) -> (2,2) -> (3,3)
Total distance=1.41+1.41+1.41=4.23

This is the path with minimum distance.
Your approach only looked at the local minimum. However, you should be looking for the global minimum. Hope you understood!

6 Likes