Friki en un laberinto

Geek está en un laberinto de tamaño N*M . Cada celda del laberinto está formada por ‘.’ o ‘#’. Una celda vacía se representa con ‘.’ y un obstáculo está representado por ‘#’ . La tarea es averiguar cuántas celdas vacías diferentes puede atravesar Si Geek comienza en la celda (R, C) y evita los obstáculos y puede moverse en cualquiera de las cuatro direcciones, pero puede moverse hacia arriba como máximo U veces y él puede moverse hacia abajo como máximo D veces. 

Ejemplos:

Entrada:  N = 3, M = 3, 
R = 1, C = 0
U = 1, D = 1
mat = {{. . .}, {. #.}, {#. .}}
Salida : 5
Explicación : Geek puede alcanzar 
(1, 0), (0, 0), (0, 1), (0, 2), (1, 2) 

Entrada:  N = 3, M = 4, R = 1, C = 0, U = 1, D = 2 
mat = {{. . .}, {. #.}, {. . .}, {#. .}} 
Salida : 10
Explicación: Geek puede llegar a todas las 
celdas excepto a los obstáculos.

Planteamiento: La idea para solucionar este problema se basa en la siguiente idea:

Continúe moviéndose radialmente en las cuatro direcciones (arriba, abajo, izquierda, derecha) y siga contando el número de giros tomados para moverse hacia arriba y hacia abajo. Si el número de vueltas que quedan para los movimientos ascendentes y descendentes dados no es 0, muévase hacia arriba y hacia abajo y siga contando las celdas vacías.

Siga los pasos mencionados a continuación para implementar la idea:

• Compruebe si el punto de partida está bloqueado por un obstáculo (#)
  •  Si es verdadero, devuelve 0 .
• Mantenga una cola de arrays para almacenar filas, columnas, altibajos para cualquier celda.
• Haz un recorrido BFS :
  • Verifique si la celda está vacía y luego incremente la variable de conteo (digamos cnt ).
  • Compruebe si queda algún movimiento hacia arriba o no.
    • Si quedan movimientos hacia arriba , muévase hacia arriba y disminuya el conteo de movimientos hacia arriba y empuje el estado actual de la celda en la cola.
  • Compruebe si queda algún movimiento hacia abajo o no.
    • Si se dejan movimientos hacia abajo, muévase hacia abajo y disminuya el conteo de movimientos hacia abajo y empuje el estado actual de la celda en la cola.
• Finalmente, devuelva el cnt .

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count different empty cells 
// he can pass through while avoiding
// the obstacles
int numberOfCells(int n, int m, int r,
                  int c, int u, int d,
                  vector<vector<char> >& mat)
{
    // If cell having Obstacle
    if (mat[r] == '#')
        return 0;
 
    queue<vector<int> > que;
    int cnt = 0;
    int i = 0;
    int j = 0;
 
    mat[r] = '#';
    que.push({ r, c, u, d });
 
    // BFS traversal of the matrix
    while (que.size()) {
        auto& f = que.front();
        int rr = f[0];
        int cc = f[1];
        int uu = f[2];
        int dd = f[3];
        que.pop();
 
        ++cnt;
 
        // Move left
        i = rr;
        j = cc - 1;
        if (0 <= j && mat[i][j] == '.') {
 
            // Mark the cell visited
            mat[i][j] = '#';
            que.push({ i, j, uu, dd });
        }
 
        // Move right
        i = rr;
        j = cc + 1;
        if (j < m && mat[i][j] == '.') {
 
            // Mark the cell visited
            mat[i][j] = '#';
            que.push({ i, j, uu, dd });
        }
 
        // Move up
        i = rr - 1;
        j = cc;
        if (0 <= i && mat[i][j] == '.' && uu) {
 
            // Mark the cell visited
            mat[i][j] = '#';
            que.push({ i, j, uu - 1, dd });
        }
 
        // Move down
        i = rr + 1;
        j = cc;
        if (i < n && mat[i][j] == '.' && dd) {
 
            // Mark the cell visited
            mat[i][j] = '#';
            que.push({ i, j, uu, dd - 1 });
        }
    }
 
    // Return the count
    return cnt;
}
 
// Driver code
int main()
{
    int N = 3, M = 3, R = 1, C = 0;
    int U = 1, D = 1;
    vector<vector<char> > mat = { { '.', '.', '.' },
                                  { '.', '#', '.' },
                                  { '#', '.', '.' } };
 
    // Function call
    cout << numberOfCells(N, M, R, C, U, D, mat);
    return 0;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
    // Function to count different empty cells 
    // he can pass through while avoiding
    // the obstacles
    public static int numberOfCells(int n, int m, int r, int c, int u, int d, ArrayList<ArrayList<Character>> mat)
    {
        // If cell having Obstacle
        if (mat.get(r).get(c) == '#')
            return 0;
 
        Queue<ArrayList<Integer>> que = new ArrayDeque<ArrayList<Integer>>();
        int cnt = 0;
        int i = 0;
        int j = 0;
 
        mat.get(r).set(c, '#');
        que.add(new ArrayList<Integer>(List.of(r, c, u, d)));
 
        // BFS traversal of the matrix
        while (!que.isEmpty()) {
            ArrayList<Integer> f = que.peek();
            int rr = f.get(0);
            int cc = f.get(1);
            int uu = f.get(2);
            int dd = f.get(3);
            que.remove();
 
            ++cnt;
 
            // Move left
            i = rr;
            j = cc - 1;
            if (0 <= j && mat.get(i).get(j) == '.') {
 
                // Mark the cell visited
                mat.get(i).set(j, '#');
                que.add(new ArrayList<Integer>(List.of(i, j, uu, dd)));
            }
 
            // Move right
            i = rr;
            j = cc + 1;
            if (j < m && mat.get(i).get(j) == '.') {
 
                // Mark the cell visited
                mat.get(i).set(j, '#');
                que.add(new ArrayList<Integer>(List.of(i, j, uu, dd)));
            }
 
            // Move up
            i = rr - 1;
            j = cc;
            if (0 <= i && mat.get(i).get(j) == '.' && uu > 0) {
 
                // Mark the cell visited
                mat.get(i).set(j, '#');
                que.add(new ArrayList<Integer>(List.of(i, j, uu-1, dd)));
            }
 
            // Move down
            i = rr + 1;
            j = cc;
            if (i < n && mat.get(i).get(j) == '.' && dd > 0) {
 
                // Mark the cell visited
                mat.get(i).set(j, '#');
                que.add(new ArrayList<Integer>(List.of(i, j, uu, dd-1)));
            }
        }
 
        // Return the count
        return cnt;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int N = 3, M = 3, R = 1, C = 0;
        int U = 1, D = 1;
        ArrayList<ArrayList<Character>> mat = new ArrayList<ArrayList<Character>>(
            List.of(new ArrayList<Character>(
                List.of('.', '.', '.')
            ),
            new ArrayList<Character>(
                List.of('.', '#', '.')
            ),
            new ArrayList<Character>(
                List.of('#', '.', '.')
            ))
        );
 
        // Function call
        System.out.println(numberOfCells(N, M, R, C, U, D, mat));
    }
}
 
// This code is contributed by subhamgoyal2014.

5

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)