Celdas mínimas atravesadas para llegar a la esquina donde cada celda representa saltos

Supongamos que A está en la posición (0, 0) de una cuadrícula bidimensional que contiene ‘m’ filas y ‘n’ columnas. Su objetivo es llegar al punto inferior derecho de esta cuadrícula atravesando el menor número de celdas posible.
Cada celda de la cuadrícula contiene un número entero positivo que define el número de celdas que A puede saltar hacia la derecha o hacia abajo cuando llega a esa celda.
Encuentre el número mínimo de celdas que deben tocarse para llegar a la esquina inferior derecha.

Ejemplos: 

Input : 2 4 2
        5 3 8
        1 1 1
Output :
So following two paths exist to reach (2, 2) from (0, 0)
(0, 0) => (0, 2) => (2, 2) 
(0, 0) => (2, 0) => (2, 1) => (2, 2) 

Hence the output for this test case should be 3 

La siguiente es una solución Breadth First Search (BFS) del problema: 

1. Piense en esta array como un árbol y (0, 0) como raíz y aplique BFS usando el recorrido de orden de niveles.
2. Empuje las coordenadas y el número de saltos en una cola.
3. Abre la cola después de cada nivel del árbol.
4. Agregue el valor en la celda a las coordenadas mientras se desplaza hacia la derecha y hacia abajo.
5. Devuelva el número de celdas tocadas mientras salta cuando llega a la esquina inferior derecha.

Implementación:

// C++ program to reach bottom right corner using
// minimum jumps.
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 3
 
// function to check coordinates are in valid range.
bool safe(int x, int y)
{
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
 
// function to return minimum no of cells to reach
// bottom right cell.
int matrixJump(int M[R][C], int R1, int C1)
{
    queue<pair<int, pair<int, int> > > q;
 
    // push the no of cells and coordinates in a queue.
    q.push(make_pair(1, make_pair(R1, C1)));
 
    while (!q.empty()) {
        int x = q.front().second.first; // x coordinate
        int y = q.front().second.second; // y coordinate
        int no_of_cells = q.front().first; // no of cells
 
        q.pop();
 
        // when it reaches bottom right return no of cells
        if (x == R - 1 && y == C - 1)           
            return no_of_cells;
 
        int v = M[x][y];
 
        if (safe(x + v, y))
            q.push(make_pair(no_of_cells + 1, make_pair(x + v, y)));
 
        if (safe(x, y + v))
            q.push(make_pair(no_of_cells + 1, make_pair(x, y + v)));
    }
 
    // when destination cannot be reached
    return -1;
}
 
// driver function
int main()
{
    int M[R][C] = { { 2, 4, 2 },
                    { 5, 3, 8 },
                    { 1, 1, 1 } };
    cout << matrixJump(M, 0, 0);
    return 0;
}

// Java program to reach bottom right corner
// using minimum jumps.
import java.util.*;
 
class GFG
{
static int R = 3, C = 3;
 
// function to check coordinates are in valid range.
static boolean safe(int x, int y)
{
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
 
// pair class
static class pair<T, R>
{
    T first;
    R second;
    pair(T t, R r)
    {
        first = t;
        second = r;
    }
}
 
// function to return minimum no of cells
// to reach bottom right cell.
static int matrixJump(int M[][], int R1, int C1)
{
    Queue<pair<Integer,
          pair<Integer,
               Integer>>> q = new LinkedList<>();
 
    // push the no of cells and coordinates in a queue.
    q.add(new pair(1, new pair(R1, C1)));
 
    while (q.size() > 0)
    {
        int x = q.peek().second.first; // x coordinate
        int y = q.peek().second.second; // y coordinate
        int no_of_cells = q.peek().first; // no of cells
 
        q.remove();
 
        // when it reaches bottom right return no of cells
        if (x == R - 1 && y == C - 1)        
            return no_of_cells;
 
        int v = M[x][y];
 
        if (safe(x + v, y))
            q.add(new pair(no_of_cells + 1,
                  new pair(x + v, y)));
 
        if (safe(x, y + v))
            q.add(new pair(no_of_cells + 1,
                  new pair(x, y + v)));
    }
 
    // when destination cannot be reached
    return -1;
}
 
// Driver Code
public static void main(String ars[])
{
    int M[][] = {{ 2, 4, 2 },
                 { 5, 3, 8 },
                 { 1, 1, 1 }};
    System.out.print( matrixJump(M, 0, 0));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to reach bottom
# right corner using minimum jumps.
 
R, C = 3, 3
 
# Function to check coordinates are in valid range.
def safe(x, y):
 
    if x < R and y < C and x >= 0 and y >= 0:
        return True
    return False
 
# Function to return minimum no of
# cells to reach bottom right cell.
def matrixJump(M, R1, C1):
 
    q = []
 
    # push the no of cells and coordinates in a queue.
    q.append((1, (R1, C1)))
 
    while len(q) != 0:
        x = q[0][1][0] # x coordinate
        y = q[0][1][1] # y coordinate
        no_of_cells = q[0][0] # no of cells
 
        q.pop(0)
 
        # when it reaches bottom right return no of cells
        if x == R - 1 and y == C - 1:        
            return no_of_cells
 
        v = M[x][y]
 
        if safe(x + v, y):
            q.append((no_of_cells + 1, (x + v, y)))
 
        if safe(x, y + v):
            q.append((no_of_cells + 1, (x, y + v)))
     
    # when destination cannot be reached
    return -1
 
# Driver code
if __name__ == "__main__":
 
    M = [[2, 4, 2],
        [5, 3, 8],
        [1, 1, 1]]
         
    print(matrixJump(M, 0, 0))
 
# This code is contributed by Rituraj Jain

// C# program to reach bottom right corner
// using minimum jumps.
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
     
static int R = 3, C = 3;
 
// function to check coordinates are in valid range.
static Boolean safe(int x, int y)
{
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
 
// Pair class
public class Pair<T, U>
{
    public T first;
    public U second;
    public Pair() {
    }
 
    public Pair(T first, U second)
    {
        this.first = first;
        this.second = second;
    }
 
};
 
// function to return minimum no of cells
// to reach bottom right cell.
static int matrixJump(int [,]M, int R1, int C1)
{
    Queue<Pair<int,Pair<int,int>>> q =
    new Queue<Pair<int,Pair<int,int>>>();
 
    // push the no of cells and coordinates in a queue.
    q.Enqueue(new Pair<int, Pair<int, int>>(
                1, new Pair<int, int>(R1, C1)));
 
    while (q.Count > 0)
    {
        int x = q.Peek().second.first; // x coordinate
        int y = q.Peek().second.second; // y coordinate
        int no_of_cells = q.Peek().first; // no of cells
 
        q.Dequeue();
 
        // when it reaches bottom right return no of cells
        if (x == R - 1 && y == C - 1)        
            return no_of_cells;
 
        int v = M[x, y];
 
        if (safe(x + v, y))
            q.Enqueue(new Pair<int,Pair<int,int>>(no_of_cells + 1,
                new Pair<int,int>(x + v, y)));
 
        if (safe(x, y + v))
            q.Enqueue(new Pair<int,Pair<int,int>>(no_of_cells + 1,
                new Pair<int,int>(x, y + v)));
    }
 
    // when destination cannot be reached
    return -1;
}
 
// Driver Code
public static void Main(String []ars)
{
    int [,]M = {{ 2, 4, 2 },
                { 5, 3, 8 },
                { 1, 1, 1 }};
    Console.Write( matrixJump(M, 0, 0));
}
}
 
// This code is contributed by Arnab Kundu

<script>
// Javascript program to reach bottom right corner
// using minimum jumps.
 
let R = 3, C = 3;
 
// function to check coordinates are in valid range.
function safe(x,y)
{
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
 
// pair class
class pair
{
    constructor(t,r)
    {
        this.first = t;
        this.second = r;
    }
}
 
// function to return minimum no of cells
// to reach bottom right cell.
function matrixJump(M,R1,C1)
{
    let q=[];
    // push the no of cells and coordinates in a queue.
    q.push(new pair(1, new pair(R1, C1)));
   
    while (q.length > 0)
    {
        let x = q[0].second.first; // x coordinate
        let y = q[0].second.second; // y coordinate
        let no_of_cells = q[0].first; // no of cells
   
        q.shift();
   
        // when it reaches bottom right return no of cells
        if (x == R - 1 && y == C - 1)        
            return no_of_cells;
   
        let v = M[x][y];
   
        if (safe(x + v, y))
            q.push(new pair(no_of_cells + 1,
                  new pair(x + v, y)));
   
        if (safe(x, y + v))
            q.push(new pair(no_of_cells + 1,
                  new pair(x, y + v)));
    }
   
    // when destination cannot be reached
    return -1;
}
 
// Driver Code
let M=[[ 2, 4, 2 ],[ 5, 3, 8 ],[ 1, 1, 1 ]];
document.write( matrixJump(M, 0, 0));                
                  
// This code is contributed by avanitrachhadiya2155
</script>

3

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Este artículo es una contribución de Kshitiz Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.