You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.
Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.
The Manhattan distance between two points (x1, y1) and (x2, y2) is abs(x1 - x2) + abs(y1 - y2).
Example 1:
Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] Output: 2 Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.
Example 2:
Input: x = 3, y = 4, points = [[3,4]] Output: 0 Explanation: The answer is allowed to be on the same location as your current location.
Example 3:
Input: x = 3, y = 4, points = [[2,3]] Output: -1 Explanation: There are no valid points.
Constraints:
1 <= points.length <= 104points[i].length == 21 <= x, y, ai, bi <= 104program main
implicit none
integer :: x, y, i, n, ans
integer, dimension(:, :), allocatable :: points
read(*, *) x, y, n
allocate(points(n, 2))
do i = 1, n
read(*, *) points(i, :)
end do
ans = solve(x, y, points)
write(*, '(I0)') ans
contains
function solve(x, y, points) result(ans)
implicit none
integer, intent(in) :: x, y, points(:, :)
integer :: i, j, k, m, n, ans
logical :: found
ans = -1
found = .false.
do i = 1, size(points, 1)
if (points(i, 1) == x .or. points(i, 2) == y) then
found = .true.
exit
end if
end do
if (.not. found) return
ans = i - 1
do j = 1, size(points, 1)
if (j /= i) then
m = abs(points(i, 1) - points(j, 1))
n = abs(points(i, 2) - points(j, 2))
if (m + n < ans) then
ans = m + n
end if
end if
end do
end function solve
end program mainAt line 7 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x787a8f164960 in ??? #1 0x787a8f1654d9 in ??? #2 0x787a8f3b917b in ??? #3 0x787a8f3b2684 in ??? #4 0x787a8f3b32aa in ??? #5 0x5d3fe72635f8 in MAIN__ #6 0x5d3fe7263a06 in main
module FindClosestValidPoint
implicit none
contains
function find_closest_valid_point(x, y, points) result(closest_point)
implicit none
integer, intent(in) :: x, y, points(:, :)
integer :: closest_point
integer :: i, j, d1, d2, min_d, min_i
! Initialize closest point to -1
closest_point = -1
! Loop through all points
do i = 1, size(points, 1)
! Check if point is valid
if (points(i, 1) == x .or. points(i, 2) == y) then
! Calculate Manhattan distance
d1 = abs(x - points(i, 1))
d2 = abs(y - points(i, 2))
min_d = min(d1, d2)
! If this is the first valid point or the current minimum distance is greater than the current distance
if (closest_point == -1 .or. min_d < min_d) then
! Update closest point and minimum distance
closest_point = i
min_d = min_d
end if
end if
end do
! Return closest point
closest_point = closest_point
end function find_closest_valid_point
end module FindClosestValidPoint
program test_find_closest_valid_point
use FindClosestValidPoint
implicit none
integer :: x, y, points(3, 2)
integer :: closest_point
! Test case 1:
x = 3
y = 4
points = reshape([1, 2, 3, 1, 2, 4, 2, 3, 4, 4], [3, 2])
closest_point = find_closest_valid_point(x, y, points)
write (*, *) "Closest point for (", x, ", ", y, ") is: ", closest_point
! Test case 2:
x = 3
y = 4
points = reshape([3, 4], [1, 2])
closest_point = find_closest_valid_point(x, y, points)
write (*, *) "Closest point for (", x, ", ", y, ") is: ", closest_point
! Test case 3:
x = 3
y = 4
points = reshape([2, 3], [1, 2])
closest_point = find_closest_valid_point(x, y, points)
write (*, *) "Closest point for (", x, ", ", y, ") is: ", closest_point
end program test_find_closest_valid_point
temp.f95:54:4:
54 | points = reshape([3, 4], [1, 2])
| 1
Error: Different shape for array assignment at (1) on dimension 1 (3 and 1)
temp.f95:61:4:
61 | points = reshape([2, 3], [1, 2])
| 1
Error: Different shape for array assignment at (1) on dimension 1 (3 and 1)
def nearestValidPoint(x: int, y: int, points: List[List[int]]) -> int:
min_distance = float("inf")
index = -1
for i, point in enumerate(points):
if x == point[0] or y == point[1]:
distance = abs(x - point[0]) + abs(y - point[1])
if distance < min_distance:
min_distance = distance
index = i
return index
Iterate through each point in the points array, checking if its x or y coordinate is the same as the input x or y coordinate, making the point a valid point. If the point is valid, calculate the Manhattan distance between the input point and the current point. If the calculated distance is smaller than the current minimum distance, update the minimum distance and store the index of the current point. After iterating through all points, return the index of the point with the smallest Manhattan distance. If no point is valid, return -1.
int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
int min_distance = INT_MAX, index = -1;
for (int i = 0; i < points.size(); i++) {
if (x == points[i][0] || y == points[i][1]) {
int distance = abs(x - points[i][0]) + abs(y - points[i][1]);
if (distance < min_distance) {
min_distance = distance;
index = i;
}
}
}
return index;
}
Iterate through each point in the points array, checking if its x or y coordinate is the same as the input x or y coordinate, making the point a valid point. If the point is valid, calculate the Manhattan distance between the input point and the current point. If the calculated distance is smaller than the current minimum distance, update the minimum distance and store the index of the current point. After iterating through all points, return the index of the point with the smallest Manhattan distance. If no point is valid, return -1.