Проверить, можно ли добраться до конца массива из заданной позиции

Опубликовано: 9 Января, 2022

Для массива arr [] из N натуральных чисел и числа S задача состоит в том, чтобы добраться до конца массива по индексу S. Мы можем только перейти от текущего индекса i к индексу (i + arr [i]) или (i - arr [i]) . Если есть способ добраться до конца массива, то выведите «Да», иначе выведите «Нет» .
Примеры:

Input: arr[] = {4, 1, 3, 2, 5}, S = 1 
Output: Yes 
Explanation: 
initial position: arr[S] = arr[1] = 1. 
Jumps to reach the end: 1 -> 4 -> 5 
Hence end has been reached. 
Input: arr[] = {2, 1, 4, 5}, S = 2 
Output: No 
Explanation: 
initial position: arr[S] = arr[2] = 2. 
Possible Jumps to reach the end: 4 -> (index 7) or 4 -> (index -2) 
Since both are out of bounds, Hence end can’t be reached. 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход 1. Эту проблему можно решить с помощью поиска в ширину. Ниже приведены шаги:

  • Считайте начальный индекс S как исходный узел и вставьте его в очередь.
  • Пока очередь не пуста, сделайте следующее:
    1. Вытолкнуть элемент из верхней части очереди, скажем, temp .
    2. Если temp уже посещен или это массив вне привязанного индекса, перейдите к шагу 1.
    3. В противном случае отметьте его как посещенное.
    4. Теперь, если temp является последним индексом массива, выведите «Yes» .
    5. В противном случае возьмите два возможных места назначения от temp до (temp + arr [temp]) , (temp - arr [temp]) и поместите их в очередь.
  • Если после вышеперечисленных шагов конец массива не достигнут, выведите «Нет» .

Below is the implementation of the above approach: 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if we can reach to
// the end of the arr[] with possible moves
void solve(int arr[], int n, int start)
{
 
    // Queue to perform BFS
    queue<int> q;
 
    // Initially all nodes(index)
    // are not visited.
    bool visited[n] = { false };
 
    // Initially the end of
    // the array is not reached
    bool reached = false;
 
    // Push start index in queue
    q.push(start);
 
    // Untill queue becomes empty
    while (!q.empty()) {
 
        // Get the top element
        int temp = q.front();
 
        // Delete popped element
        q.pop();
 
        // If the index is already
        // visited. No need to
        // traverse it again.
        if (visited[temp] == true)
            continue;
 
        // Mark temp as visited
        // if not
        visited[temp] = true;
        if (temp == n - 1) {
 
            // If reached at the end
            // of the array then break
            reached = true;
            break;
        }
 
        // If temp + arr[temp] and
        // temp - arr[temp] are in
        // the index of array
        if (temp + arr[temp] < n) {
            q.push(temp + arr[temp]);
        }
 
        if (temp - arr[temp] >= 0) {
            q.push(temp - arr[temp]);
        }
    }
 
    // If reaches the end of the array,
    // Print "Yes"
    if (reached == true) {
        cout << "Yes";
    }
 
    // Else print "No"
    else {
        cout << "No";
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 4, 1, 3, 2, 5 };
 
    // Starting index
    int S = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    solve(arr, N, S);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if we can reach to
// the end of the arr[] with possible moves
static void solve(int arr[], int n, int start)
{
 
    // Queue to perform BFS
    Queue<Integer> q = new LinkedList<>();
 
    // Initially all nodes(index)
    // are not visited.
    boolean []visited = new boolean[n];
 
    // Initially the end of
    // the array is not reached
    boolean reached = false;
 
    // Push start index in queue
    q.add(start);
 
    // Untill queue becomes empty
    while (!q.isEmpty())
    {
 
        // Get the top element
        int temp = q.peek();
 
        // Delete popped element
        q.remove();
 
        // If the index is already
        // visited. No need to
        // traverse it again.
        if (visited[temp] == true)
            continue;
 
        // Mark temp as visited
        // if not
        visited[temp] = true;
         
        if (temp == n - 1)
        {
 
            // If reached at the end
            // of the array then break
            reached = true;
            break;
        }
 
        // If temp + arr[temp] and
        // temp - arr[temp] are in
        // the index of array
        if (temp + arr[temp] < n)
        {
            q.add(temp + arr[temp]);
        }
 
        if (temp - arr[temp] >= 0)
        {
            q.add(temp - arr[temp]);
        }
    }
 
    // If reaches the end of the array,
    // Print "Yes"
    if (reached == true)
    {
        System.out.print("Yes");
    }
 
    // Else print "No"
    else
    {
        System.out.print("No");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 4, 1, 3, 2, 5 };
 
    // Starting index
    int S = 1;
    int N = arr.length;
 
    // Function call
    solve(arr, N, S);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach
from queue import Queue
  
# Function to check if we can reach to
# the end of the arr[] with possible moves
def solve(arr, n, start):
  
    # Queue to perform BFS
    q = Queue()
  
    # Initially all nodes(index)
    # are not visited.
    visited = [False] * n
    
    # Initially the end of
    # the array is not reached
    reached = False
    
    # Push start index in queue
    q.put(start);
  
    # Untill queue becomes empty
    while (not q.empty()):
  
        # Get the top element
        temp = q.get()
  
        # If the index is already
        # visited. No need to
        # traverse it again.
        if (visited[temp] == True):
            continue
  
        # Mark temp as visited, if not
        visited[temp] = True
        if (temp == n - 1):
  
            # If reached at the end
            # of the array then break
            reached = True
            break
  
        # If temp + arr[temp] and
        # temp - arr[temp] are in
        # the index of array
        if (temp + arr[temp] < n):
            q.put(temp + arr[temp])
  
        if (temp - arr[temp] >= 0):
            q.put(temp - arr[temp])
  
    # If reaches the end of the array,
    # Print "Yes"
    if (reached == True):
        print("Yes")
  
    # Else print "No"
    else:
        print("No")
  
# Driver code
if __name__ == "__main__":
  
    # Given array arr[]
    arr = [ 4, 1, 3, 2, 5 ]
  
    # starting index
    S = 1
    N = len(arr)
  
    # Function call
    solve(arr, N, S)
  
# This code is contributed by himanshu77

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if we can reach to
// the end of the []arr with possible moves
static void solve(int []arr, int n,
                  int start)
{
 
    // Queue to perform BFS
    Queue<int> q = new Queue<int>();
 
    // Initially all nodes(index)
    // are not visited.
    bool []visited = new bool[n];
 
    // Initially the end of
    // the array is not reached
    bool reached = false;
 
    // Push start index in queue
    q.Enqueue(start);
 
    // Untill queue becomes empty
    while (q.Count != 0)
    {
 
        // Get the top element
        int temp = q.Peek();
 
        // Delete popped element
        q.Dequeue();
 
        // If the index is already
        // visited. No need to
        // traverse it again.
        if (visited[temp] == true)
            continue;
 
        // Mark temp as visited
        // if not
        visited[temp] = true;
         
        if (temp == n - 1)
        {
 
            // If reached at the end
            // of the array then break
            reached = true;
            break;
        }
 
        // If temp + arr[temp] and
        // temp - arr[temp] are in
        // the index of array
        if (temp + arr[temp] < n)
        {
            q.Enqueue(temp + arr[temp]);
        }
 
        if (temp - arr[temp] >= 0)
        {
            q.Enqueue(temp - arr[temp]);
        }
    }
 
    // If reaches the end of the array,
    // Print "Yes"
    if (reached == true)
    {
        Console.Write("Yes");
    }
 
    // Else print "No"
    else
    {
        Console.Write("No");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 4, 1, 3, 2, 5 };
 
    // Starting index
    int S = 1;
    int N = arr.Length;
 
    // Function call
    solve(arr, N, S);
}
}
 
// This code is contributed by gauravrajput1
Output: 

Yes

Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023