Robot in una griglia

Qualcosa di interessante accade quando chiediamo "Cosa succede se torniamo indietro?".

Quindi vogliamo andare da A (i + j, j) - > A (i, j) per andare a sinistra e A (i, i + j) - > A (i, j) per salire. Dal momento che le cose potrebbero diventare confuse se continuassi ad usare i e j, userò x e y, e dirò che stiamo andando indietro da A (x, y) se stiamo andando a sinistra o in alto.

Riceviamo queste formule:

Left: A(x, y) -> A(x-y, y)

Up: A(x, y) -> A(x, y-x)

Prima cosa da notare: se x = y, allora otteniamo una coordinata 0 in entrambe le formule, quindi sappiamo che qualsiasi cosa sulla diagonale che non è il nostro punto di partenza è irraggiungibile.

Seconda cosa da notare: abbiamo x-y in una formula e y-x nell'altra. Poiché xey sono sempre positivi, almeno una delle due possibili posizioni da cui potremmo provenire è impossibile .

Ciò significa che possiamo calcolare esattamente da quale quadrato veniamo, a meno che il quadrato non sia raggiungibile, nel qual caso si tratta di un quadrato diagonale o di un quadrato diagonale. Tornando indietro da un quadrato raggiungibile, otteniamo il percorso solo , che deve essere il percorso con la lunghezza minore.

Quanto segue è la mia soluzione al problema originariamente presentato:

C'è un solo modo in cui j può cambiare e quando lo fa, aumenta di 1 perché il robot si sposta a destra. Sappiamo che è iniziato all'1 e si è concluso a n, quindi sappiamo quanti passi ci sono voluti a destra.

La stessa cosa con me e i passi verso il basso.

Quale percorso è irrilevante.

Questo è un problema di programmazione dinamica. L'idea è di provare tutti i percorsi e restituire il numero minimo di passaggi eseguiti ogni volta.

int MinSteps( int posX, int posY, int destX, int destY)
{
    // if we reached the destination
    if (posX == destX && posY == destY)
      return 0;

     // if we didn't reach the dest we need to penalize this path so we return INT_MAX
    if (posX >= arraySizeX || posY >= arraySizeY )
     return INT_MAX;

  return min( MinSteps(posX+posY, posY), MinSteps(posX, posY+posX) ) + 1;
}

Dal momento che stiamo ricalcolando più volte lo stesso percorso, l'ottimizzazione ovvia è quella di utilizzare la memoizzazione per memorizzare i passaggi minimi necessari fino ad ora.

// Table should be init with INT_MAX except the first column with 0.
int MinSteps( int posX, int posY, int destX, int destY, int** table)
{
    // if we reached the destination
    if (posX == destX && posY == destY)
      return 0;

     // if we didn't reach the dest, we need to penalize this path so we return INT_MAX
    if (posX >= arraySizeX || posY >= arraySizeY )
     return INT_MAX;

   // If we already calculate this paths min steps we only look it up
   if (table[posX][posY] != INT_MAX)
    return table[posX][posY];

  table[posX][posY]= min( MinSteps(posX+posY, posY), MinSteps(posX, posY+posX) ) + 1;
}

Questo può essere facilmente forzato a forza bruta usando la ricerca in ampiezza.

Algoritmo più semplice usando la coda. La performance potrebbe essere migliorata ricordando i punti che erano già stati visitati. E poiché stai usando breath-first, sei sicuro che i luoghi visitati in precedenza fossero più vicini. (mi dispiace per il codice C #).

    private struct Location
    {
        public int X { get; set; }
        public int Y { get; set; }
        public int Distance { get; set; }
    }

    public static int minSteps(int m, int n)
    {
        Queue<Location> locations = new Queue<Location>();
        locations.Enqueue(new Location(){X = 1, Y = 1, Distance = 0});

        while(locations.Count > 0)
        {
            var loc = locations.Dequeue();

            // if it reached the target location
            if(loc.X == m && loc.Y == n)
            {
                return loc.Distance;
            }

            // if we went past the location then this path is invalid
            if(loc.X > m || loc.Y > n)
                continue;

            locations.Enqueue(new Location{ X = loc.X + loc.Y, Y = loc.Y, Distance = loc.Distance+1});
            locations.Enqueue(new Location{ X = loc.X, Y = loc.X + loc.Y, Distance = loc.Distance + 1 });
        }

        throw new Exception("No path found!");
    }

Eccone uno - e mi è stato detto che è sulla falsariga di ciò che l'intervistatore stava cercando

1.) If m > n, then m-=n i.e. he could only have come from (m-n,n)

2.) Else if m < n, then n-=m i.e. he could only have come from (m,n-m)

and this is followed by the edge cases and housekeeping

 int minSteps(int m, int n)
        {
            if(m<=1 || n <=1) return -1;
            int count = 0;
            while(abs(m-n) && m>=1 && n>=1)
            {
                if(m>n)
                    m=m-n;
                else n = n-m;
                count++;
            }
            if(m==1 && n==1)
                return count;
            else return -1;
        }

Questo è tratto da qui

Ecco la soluzione migliore con la complessità temporale minima di O (mn).

import java.util.Scanner;

public class Robot4x4 
{
    public static void main(String[] args) 
    {
        int a[][]=new int [4][4];
        int p=count(a,4,4);
        System.out.println("Total Path are:"+p);
    }

    public static int count(int a[][],int m,int n)
    {
        int p[][]=new int [m][n];
        for(int i=0;i<m;i++)
            p[i][0]=1;
        for(int j=0;j<n;j++)
            p[0][j]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                p[i][j]=p[i-1][j]+p[i][j-1];
        return p[m-1][n-1];
    }
}

Se hai dubbi sulla logica, guarda questo video che ti aiuterà a capire: link