FindShortestPath

/*
warmup questions:

1. process vs thread?

2. What are the benefits of multithreaded programming? 

3. What is deadlock? How to fix it?


Basic Question

We have a 2D map consisting of cells. There's a cell that is the starting point and a cell that is the destination. 
A character is put at the starting point and can move up, down, left or right in each step. 
Each cell in the map could be either empty or occupied by a wall. The character can only move to an empty cell.

The goal is to find the shortest path for the character from the starting point to the destination.


010
010
000

Time: O(m*n) 
Space: O(m*n)

*/

int[] directions = {-1,0 , 1,0, 0,-1, 0,1};

class Cell {
  int[] pos;
  List<int[]> shortest;
  
  
  public Cell(...) {
  }
}

public List<int[]> findShortestPath(int[][] grid) {
  
  Queue<int[]> nextPos = new LinkedList<>();
  Set<int[]> 
    = new HashSet<>();
  nextPos.add(new int[]{0,0});
  
  int m = grid.length(), n = grid[0].length();
  List<int[]> shortest = new ArrayList<>();
  shortest.add(new int[]{0,0});
  
  int curr = 1;
  while(!nextPos.isEmpty()) {
    curr++;
    for (int i=0; i < nextPos.length(); i++) {
      Cell nextCell = nextPos.poll();
      int x = nextCell.pos[0], y = nextCell.pos[1];
      List<int[]> shortest = nextCell.shortest;
      
      if (grid[x][y] == new int[]{m-1, n-1}) { // at destination
         return shortest;
      }
      
      // Explore directions
      for (int j=0; j<directions.length; j+=2) {
        int newX = x + directions[j];
        int newY = y + directions[j+1];
        int[] newPos = new int[]{newX, newY};
        
        if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited.contains(newPost) || grid[newX][newY] == 1) {
          continue;
        }
        
        List<int[]> newShortest = shortest;
        newShortest.add(newPos);
        Cell cell = new Cell(newPos, newShortest);
        
        nextPos.add(cell);
      }
    }
  }
  return null;
}



/*
Follow-up Question 1

Now we give the character a gun/tool that can destroy an adjacent wall --- if there's a wall that is adjacent to the character, 
the character can choose to destroy the wall and make the cell empty, so that the character can move freely to that cell. 
Because it is a gun (or some tool with finite life time), the character can only carry ONE bullet with them. 
This means there are at most 1 wall that can be destroyed.

The goal is to find the shortest path for the character from the starting point to the destination.

Example:

S X X X X
E E E X X
X X E X X
E E E X X
E X X X X
E E E E D (9 steps)

If you break the wall at (4, 2) or (2, 0)


*/

int[] directions = {-1,0 , 1,0, 0,-1, 0,1};

class Cell {
  int[] pos;
  List<int[]> shortest;
  int bullet; 
  
  public Cell(...) {
  }
}

public List<int[]> findShortestPath(int[][] grid) {
  
  Queue<Cell> nextPos = new LinkedList<>();
  Set<String> visited = new HashSet<>();
  nextPos.add(new int[]{0,0});
  
  int m = grid.length(), n = grid[0].length();
  List<int[]> shortest = new ArrayList<>();
  shortest.add(new int[]{0,0});
  
  int curr = 1;
  while(!nextPos.isEmpty()) {
    curr++;
    for (int i=0; i < nextPos.length(); i++) {
      Cell nextCell = nextPos.poll();
      int x = nextCell.pos[0], y = nextCell.pos[1];
      List<int[]> shortest = nextCell.shortest;
      int bullet = nextCell.bullet;
      
      if (grid[x][y] == new int[]{m-1, n-1}) { // at destination
         return shortest;
      }
      
      // Explore directions
      for (int j=0; j<directions.length; j+=2) {
        int newX = x + directions[j];
        int newY = y + directions[j+1];
        int[] newPos = new int[]{newX, newY};
        
        if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited.contains(newPost)) {
          continue;
        }
        
        List<int[]> newShortest = shortest;
        newShortest.add(newPos);
        Cell cell = new Cell(newPos, newShortest, bullet);
        
        if (bullet > 0 && grid[newX][newY] == 1) {
          Cell cell2 = new Cell(newPos, newShortest, bullet-1);
          visited.add(cell.pos.toString() + " " + cell.bullet-1);
          nextPos.add(cell2);
        }
        
        visited.add(cell.pos.toString() + " " + cell.bullet);
        nextPos.add(cell);
      }
    }
  }
  return null;
}


/*

follow-up 2

Imagine the array is 1m x 1m, 

int[][] grid -> List<int[]> obstalces, int m, int n

A star
*/