### Problem Statement :

```You are given integers sx, sy, ex, ey and two-dimensional list of integers roads.

You are currently located at coordinate (sx, sy) and want to move to destination (ex, ey).

Each element in roads contains (x, y) which is a road that will be added at that coordinate.

You can only move to adjacent (up, down, left, right) coordinates if there is a road in that coordinate or if it's the destination coordinate. For example, at (x, y) we can move to (x + 1, y) if (x + 1, y) is a road or the destination.

Return the minimum number of roads in order that must be added before there is a path consisting of roads that allows us to get to (ex, ey) from (sx, sy). If there is no solution, return -1.

Constraints

0 ≤ n ≤ 100,000 where n is the length of roads

Example 1

Input
sx = 0

sy = 0

ex = 1

ey = 2

[9, 9],

[0, 1],

[0, 2],

[0, 3],

[3, 3]

]

Output

3

Explanation

We need to add the first three roads which allows us to go from (0, 0), (0, 1), (0, 2), (1, 2). Note that we

### Solution :

```                        ```Solution in C++ :

pair<int, int> directions[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int solve(int sx, int sy, int ex, int ey, vector<vector<int>>& roads) {

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;
q.push({0, sx, sy});

map<pair<int, int>, int> cost;
cost[{sx, sy}] = 0;

while (!q.empty()) {
auto [curr_index, x, y] = q.top();
q.pop();

if (x == ex && y == ey) return curr_index;
for (auto [dx, dy] : directions) {
int nx = x + dx;
int ny = y + dy;
if (!cost.count({nx, ny}) || cost[{nx, ny}] > max(Roads[{nx, ny}], curr_index)) {
cost[{nx, ny}] = max(Roads[{nx, ny}], curr_index);
q.push({cost[{nx, ny}], nx, ny});
}
}
}
}

return -1;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int sx, int sy, int ex, int ey, int[][] roads) {
if (sx == ex && sy == ey) {
return 0;
}

// We sort by the number of roads the current destination needs
Queue<int[]> q = new PriorityQueue<>((a, b) -> a - b);

// Use to hash/store each road
long time = (long) (1e9);

// The has for target
long target = ex * time + ey;

Map<Long, Integer> road = new HashMap<>();
Set<Long> visit = new HashSet<>();

// Store each road into the map
int count = 1;
for (int[] row : roads) {
road.put(row * time + row, count++);
}

// [x , y , number of roads]

q.offer(new int[] {sx, sy, 0});

while (!q.isEmpty()) {
int[] cur = q.poll();
long num = cur * time + cur;

// If visited, skip
if (visit.contains(num)) {
continue;
}

// each hashcode for each move (up,down,left,right)
long num1 = (cur - 1) * time + cur;
long num2 = (cur + 1) * time + cur;
long num3 = (cur) * time + cur - 1;
long num4 = (cur) * time + cur + 1;

// if any of them is equal to the target, then we return the number of roads
if (num1 == target || num2 == target || num3 == target || num4 == target) {
return cur;
}

// If the road map contains up/down/left/right move, put it into the pq with the number
// of roads it need to build.

q.offer(new int[] {cur - 1, cur, Math.max(cur, road.get(num1))});
}
q.offer(new int[] {cur + 1, cur, Math.max(cur, road.get(num2))});
}
q.offer(new int[] {cur, cur - 1, Math.max(cur, road.get(num3))});
}
q.offer(new int[] {cur, cur + 1, Math.max(cur, road.get(num4))});
}
}
return -1;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, sx, sy, ex, ey, roads):
parent = {}
seen = set()

# Find
def ufind(x, y):
if (x, y) not in parent:
parent[(x, y)] = (x, y)
return (x, y)
if parent[(x, y)] == (x, y):
return (x, y)

d = parent[(x, y)]
p = ufind(d, d)
parent[(x, y)] = p
return p

# Union
def uunion(x1, y1, x2, y2):
p1 = ufind(x1, y1)
p2 = ufind(x2, y2)

parent[p2] = parent[p1]

directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
for dx, dy in directions:
nx, ny = sx + dx, sy + dy
if (nx, ny) == (ex, ey):
return 0

for index, (x, y) in enumerate(roads):
# Look at neighbors
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (nx, ny) in seen:
uunion(x, y, nx, ny)

if ufind(ex, ey) == ufind(sx, sy):
return index + 1
return -1```
```

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing