package chapter_8;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RobotInAGrid2 {

  public List<Cell> findPath(int[][] grid) {
    List<Cell> path = new ArrayList<Cell>();
    Map<Cell, Boolean> cache = new HashMap<Cell, Boolean>();
    findPath(grid, grid.length - 1, grid[0].length - 1, cache, path);
    return path;
  }

  private boolean findPath(int[][] grid, int i, int j, Map<Cell, Boolean> cache, List<Cell> path) {
    Cell currentCell = new Cell(i, j);
    if (i < 0 || j < 0 || grid[i][j] == -1) {
      return false;
    } else if (i == 0 && j == 0) {
      path.add(new Cell(i, j));
      cache.put(currentCell, true);
    } else if (!cache.containsKey(currentCell)) {
      if (findPath(grid, i, j - 1, cache, path) || findPath(grid, i - 1, j, cache, path)) {
        path.add(new Cell(i, j));
        cache.put(currentCell, true);
      } else {
        cache.put(currentCell, false);
      }
    }

    return cache.get(currentCell);
  }

  public class Cell {
    int i, j;

    public Cell(int i, int j) {
      this.i = i;
      this.j = j;
    }

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + RobotInAGrid2.this.hashCode();
      result = prime * result + i;
      result = prime * result + j;
      return result;
    }

    @Override
    public String toString() {
      return i + "," + j;
    }
  }
}

@@ -196,113 +196,92 @@
     
-List
+Map
 %3CCell
-%3E path = new ArrayList%3CCell%3E();%0A    Map%3CCell, Boolean%3E cache = new HashMap%3CCell, Boolean%3E();%0A   
+, List%3CCell%3E%3E cache = new HashMap%3CCell, List%3CCell%3E%3E();%0A    List%3CCell%3E path =
  fin
@@ -334,22 +334,16 @@
 1, cache
-, path
 );%0A    r
@@ -347,16 +347,51 @@
   return
+ path == null ? new ArrayList%3C%3E() :
  path;%0A 
@@ -408,15 +408,18 @@
 ate 
-boolean
+List%3CCell%3E
  fin
@@ -465,24 +465,8 @@
 ell,
- Boolean%3E cache,
  Lis
@@ -472,21 +472,23 @@
 st%3CCell%3E
- path
+%3E cache
 ) %7B%0A    
@@ -522,16 +522,57 @@
 (i, j);%0A
+    List%3CCell%3E path = new ArrayList%3C%3E();%0A
     if (
@@ -622,21 +622,20 @@
  return 
-false
+null
 ;%0A    %7D 
@@ -720,28 +720,28 @@
 urrentCell, 
-true
+path
 );%0A    %7D els
@@ -791,16 +791,24 @@
     if (
+(path = 
 findPath
@@ -833,18 +833,29 @@
 ache
-, path) %7C%7C
+)) != null %7C%7C (path =
  fin
@@ -881,23 +881,26 @@
 j, cache
-, path)
+)) != null
 ) %7B%0A    
@@ -964,12 +964,12 @@
 ll, 
-true
+path
 );%0A 
@@ -1017,13 +1017,12 @@
 ll, 
-false
+null
 );%0A 

Implement alternate cleaner logic, Strange I think of different solutions at diff times