Harbor Ferry Route Planner

Array Easy 18 views

Like25

The Seaport dispatch team manages a fleet of ferries traveling between docks (0 to n-1). Due to heavy traffic or maintenance, certain route checkpoints are Suspended. Your mission in Harbor Ferry Route Planner is to find the Shortest Path (minimum number of docks) from an origin dock to a target dock while avoiding all suspended stations.

The "secret sauce" here is Breadth-First Search (BFS). Since each ferry hop counts as one unit of distance, BFS is the perfect algorithm to find the quickest route. You explore dock by dock, starting from the source, while skipping any path that hits a suspended dock. If a route exists, return the total count of docks in that path; if the destination is cut off, return `-1`. This planning tool is vital for keeping the harbor transit running smoothly during harbor emergencies or scheduled maintenance. It’s a classic shortest-path challenge that teaches you how to navigate networks with dynamic barriers efficiently!

When the task involves connectivity or route cost, build adjacency carefully and guard against revisiting stale states. Use a visited or best-distance structure to avoid repeated work, and ensure unreachable scenarios return the required fallback value instead of partial traversal results.

Examples

Example 1

Input

n = 4, routes = [[0,1],[1,2],[2,3]], origin = 3, max_transfers = 0

Output

Explanation

With no transfers allowed, only the starting dock receives the announcement.

Example 2

Input

n = 5, routes = [[0,1],[1,2],[2,0],[3,4]], origin = 1, max_transfers = 1

Output

Explanation

Docks 0, 1, and 2 form a reachable group within one transfer of the origin.

Example 3

Input

n = 6, routes = [[0,1],[1,2],[2,3],[3,4],[4,5]], origin = 0, max_transfers = 3

Output

Explanation

The crew may visit docks 0, 1, 2, and 3 before exceeding the transfer cap.

Algorithm Flow

Recommendation Algorithm Flow for Harbor Ferry Route Planner - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int ferry_route_reach(int n, int[][] routes, int origin, int max_transfers) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
        for (int[] route : routes) {
            graph.get(route[0]).add(route[1]);
            graph.get(route[1]).add(route[0]);
        }
        
        Set<Integer> visited = new HashSet<>();
        visited.add(origin);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{origin, 0});
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int harbor = curr[0], transfers = curr[1];
            if (transfers < max_transfers) {
                for (int neighbor : graph.get(harbor)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(new int[]{neighbor, transfers + 1});
                    }
                }
            }
        }
        
        return visited.size();
    }
}

javascript

function ferry_route_reach(n, routes, origin, max_transfers) {
    const graph = {};
    for (let i = 0; i < n; i++) graph[i] = [];
    for (const [u, v] of routes) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const visited = new Set([origin]);
    const queue = [[origin, 0]];
    
    while (queue.length > 0) {
        const [harbor, transfers] = queue.shift();
        if (transfers < max_transfers) {
            for (const neighbor of graph[harbor]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, transfers + 1]);
                }
            }
        }
    }
    
    return visited.size;
}

php

<?php
function ferry_route_reach($n, $routes, $origin, $max_transfers) {
    $graph = [];
    for ($i = 0; $i < $n; $i++) $graph[$i] = [];
    foreach ($routes as $route) {
        $graph[$route[0]][] = $route[1];
        $graph[$route[1]][] = $route[0];
    }
    
    $visited = [$origin => true];
    $queue = [[$origin, 0]];
    
    while (count($queue) > 0) {
        list($harbor, $transfers) = array_shift($queue);
        if ($transfers < $max_transfers) {
            foreach ($graph[$harbor] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $visited[$neighbor] = true;
                    $queue[] = [$neighbor, $transfers + 1];
                }
            }
        }
    }
    
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def ferry_route_reach(n: int, routes: List[List[int]], origin: int, max_transfers: int) -> int:
    graph = {i: [] for i in range(n)}
    for u, v in routes:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set([origin])
    queue = deque([(origin, 0)])
    
    while queue:
        harbor, transfers = queue.popleft()
        if transfers < max_transfers:
            for neighbor in graph[harbor]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, transfers + 1))
    
    return len(visited)

rust

use std::collections::{HashMap, HashSet, VecDeque};

pub fn ferry_route_reach(n: i32, routes: Vec<(i32, i32)>, origin: i32, max_transfers: i32) -> i32 {
    let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
    for i in 0..n {
        graph.insert(i, Vec::new());
    }
    for (u, v) in routes {
        graph.get_mut(&u).unwrap().push(v);
        graph.get_mut(&v).unwrap().push(u);
    }
    
    let mut visited = HashSet::new();
    visited.insert(origin);
    let mut queue = VecDeque::new();
    queue.push_back((origin, 0));
    
    while let Some((harbor, transfers)) = queue.pop_front() {
        if transfers < max_transfers {
            if let Some(neighbors) = graph.get(&harbor) {
                for &neighbor in neighbors {
                    if !visited.contains(&neighbor) {
                        visited.insert(neighbor);
                        queue.push_back((neighbor, transfers + 1));
                    }
                }
            }
        }
    }
    
    visited.len() as i32
}

typescript

function ferry_route_reach(n: number, routes: number[][], origin: number, max_transfers: number): number {
    const graph: { [key: number]: number[] } = {};
    for (let i = 0; i < n; i++) graph[i] = [];
    for (const [u, v] of routes) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const visited = new Set<number>([origin]);
    const queue: [number, number][] = [[origin, 0]];
    
    while (queue.length > 0) {
        const item = queue.shift();
        if (!item) break;
        const [harbor, transfers] = item;
        if (transfers < max_transfers) {
            for (const neighbor of graph[harbor]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, transfers + 1]);
                }
            }
        }
    }
    
    return visited.size;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Harbor Ferry Route Planner

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Array Problems

Longest Consecutive Sequence

Garden Relay Count

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Comments (0)

Join the Discussion