human
I am working on the file "Cap08/DesafioDSA_Solucao/Missao3/missao3_solucao.ipynb".
The first task is:
Missão: Implementar um algoritmo para mover um robô do canto superior esquerdo para o canto inferior direito de uma grade.
Nível de Dificuldade: Médio
Premissas

Existem restrições de como o robô se move?
     * O robô só pode se mover para a direita e para baixo
Algumas células são inválidas (fora dos limites)?
     * Sim
Podemos supor que as células inicial e final são células válidas?
     * Sim
Isso é uma grade retangular? ou seja, a grade não é irregular?
     * Sim
Haverá sempre uma maneira válida para o robô chegar ao canto inferior direito?
     * Não, retorno None
Podemos assumir que as entradas são válidas?
     * Não
Podemos supor que isso se encaixa na memória?
     * Sim

Teste Cases
<pre>
o = célula válida
x = célula inválida

   0  1  2  3
0  o  o  o  o
1  o  x  o  o
2  o  o  x  o
3  x  o  o  o
4  o  o  x  o
5  o  o  o  x
6  o  x  o  x
7  o  x  o  o
</pre>

Caso geral

Saída esperada = [(0, 0), (1, 0), (2, 0),
                  (2, 1), (3, 1), (4, 1),
                  (5, 1), (5, 2), (6, 2), 
                  (7, 2), (7, 3)]

Nenhum caminho válido, por exemplo, linha 7, col 2 é inválido
Nenhuma entrada
Matriz vazia

Algoritmo
To get to row r and column c [r, c], we will need to have gone:

Right from [r, c-1] if this is a valid cell - [Path 1] 
Down from [r-1, c] if this is a valid cell - [Path 2]

If we look at [Path 1], to get to [r, c-1], we will need to have gone:

Right from [r, c-2] if this is a valid cell
Down from [r-1, c-1] if this is a valid cell

Continue this process until we reach the start cell or until we find that there is no path.
Base case:

If the input row or col are < 0, or if [row, col] is not a valid cell
Return False


Recursive case:
We'll memoize the solution to improve performance.

Use the memo to see if we've already processed the current cell
If any of the following is True, append the current cell to the path and set our result to True:
We are at the start cell
We get a True result from a recursive call on:
[row, col-1]
[row-1, col]



Update the memo
Return...
Can you write Python program for it?

=====
What is a Python program to find that there is no path?
assistant
#Here is Python program to find that there is no path.

class Grid(object):

    def find_path(self, matrix):
        if matrix is None or not matrix:
            return None
        cache = {}
        path = []
        if self._find_path(matrix, len(matrix) - 1, 
                           len(matrix[0]) - 1, cache, path):
            return path
        else:
            return None

    def _find_path(self, matrix, row, col, cache, path):
        if row < 0 or col < 0 or not matrix[row][col]:
            return False
        cell = (row, col)
        if cell in cache:
            return cache[cell]
        cache[cell] = (row == 0 and col == 0 or
                       self._find_path(matrix, row, col - 1, cache, path) or
                       self._find_path(matrix, row - 1, col, cache, path))
        if cache[cell]:
            path.append(cell)
        return cache[cell]