platform 9 interview question: given a M x N matrix, you put your robot at coordinate (0, 0) (upper-left corner) and the destination is (m - 1, n - 1). Robot can only go down or right. Print all possible route from (0, 0) to (m - 1, n - 1).

WalkMatrix

public class Solution {
  
  public void entry(int m, int n) {
    Step [] steps = new Step[(m - 1) + (n - 1) + 1];
    steps[0] = new Step(0, 0);
    recur(m, n, 0, 0, steps);
  }
  
  public recur(int m, int n, int y, int x, Step [] steps) {
    if (y == m - 1 && x == n - 1) {
      for (Step s: steps) {
        System.out.print(s + " ");
      }
      System.out.println();
    } else {
      if (y + 1 < m) {
        steps[y + 1 + x] = new Step(y + 1, x);
        recur(m, n, y + 1, x, steps);
      }
      
      if (x + 1 < n) {
        steps[y + x + 1] = new Step(y, x + 1);
        recur(m, n, y, x + 1, steps);  
      }
    }
  }
  
}

class Step {
  private int row;
  private int col;
  
  public Step(int y, int x) {
    row = y;
    col = x;
  }
  
  @Override
  public String toString() {
    return String.format("(%d, %d)", y, x);
  }
}