This is No.63 in Leetcode.
My original solution is:
class Solution {
private int path = 0;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// get i and j
int i = obstacleGrid[0].length;
int j = obstacleGrid.length;
i--;
j--;
findPath(i, i, path, obstacleGrid);
return path;
}
private void findPath(int i, int j, int path, int[][] obstacleGrid){
// System.out.println("Current i and j is: " + i + ", " + j);
//end
if( i == 0 && j == 0){
// System.out.println("Reach the start");
++path;
return;
}
// obstacle
if( i < 0 || j < 0 || obstacleGrid[i][j] == 1){
// System.out.println("Dead way");
return;
}
// empty space
else{
// move left
// System.out.println("Move leftward");
findPath( i, j-1, path, obstacleGrid);
// move top
// System.out.println("Move upward");
findPath( i-1, j, path, obstacleGrid);
}
}
}Here is a problem that java is by-value language so my path can’t get updated.
However, we could see the solution given:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int R = obstacleGrid.length;
int C = obstacleGrid[0].length;
// If the starting cell has an obstacle, then simply return as there would be
// no paths to the destination.
if (obstacleGrid[0][0] == 1) {
return 0;
}
// Number of ways of reaching the starting cell = 1.
obstacleGrid[0][0] = 1;
// Filling the values for the first column
for (int i = 1; i < R; i++) {
obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
}
// Filling the values for the first row
for (int i = 1; i < C; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
}
// Starting from cell(1,1) fill up the values
// No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
// i.e. From above and left.
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
// Return value stored in rightmost bottommost cell. That is the destination.
return obstacleGrid[R - 1][C - 1];
}
}In this case, we set the obstacle grid from 1 to 0, and set the "doable" grid from 0 to 1. The number means how many paths reachable to current grid.
Ok, now it’s time to solve my original problem. For demonstrate it clearly, I write a simple test program:
public class Main{
public static void main(String[] args) {
int k = 0;
call(k);
System.out.println("k");
}
public void call( int k ){
if (k == 5){
return;
}
k++;
call(k);
}
}It has an error information as "error: non-static method call(int) cannot be referenced from a static context".
The key point here is to understand the difference between a class and an instance of that class.
From https://stackoverflow.com/questions/2559527/non-static-variable-cannot-be-referenced-from-a-static-context:
"You must understand the difference between a class and an instance of that class. If you see a car on the street, you know immediately that it’s a car even if you can’t see which model or type. This is because you compare what you see with the class "car". The class contains which is similar to all cars. Think of it as a template or an idea.
At the same time, the car you see is an instance of the class "car" since it has all the properties which you expect: There is someone driving it, it has an engine, wheels.
So the class says "all cars have a color" and the instance says "this specific car is red".
In the OO world, you define the class and inside the class, you define a field of type Color. When the class is instantiated (when you create a specific instance), memory is reserved for the color and you can give this specific instance a color. Since these attributes are specific, they are non-static.
Static fields and methods are shared with all instances. They are for values which are specific to the class and not a specific instance.
To solve your problem, you need to instantiate an instance (create an object) of your class so the runtime can reserve memory for the instance (otherwise, different instances would overwrite each other which you don’t want)."
So when I change my code to:
public class Main{
public static void main(String[] args) {
int k = 0;
//call(k);
Main myMain = new Main();
myMain.call(k);
// System.out.println("k: " + k);
}
public void call( int k ){
// System.out.println("current k is: " + k);
if (k == 5){
return;
}
k++;
call(k);
}
}It could run, but the value of k never changed. We can use static to fix this errors.
A static variable is common to all the instances (or objects) of the class because it is a class level variable. In other words you can say that only a single copy of static variable is created and shared among all the instances of the class. Memory allocation for such variables only happens once when the class is loaded in the memory.
public class Main{
static int k = 0;
public static void main(String[] args) {
Main myMain = new Main();
myMain.call();
System.out.println("k: " + k);
}
public void call(){
if (k == 5){
return;
}
k++;
call();
}
}Back to our original problem, we can change it as below:
class Solution {
private static int path = 0;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// get i and j
int i = obstacleGrid[0].length;
int j = obstacleGrid.length;
i--;
j--;
findPath(i, j, obstacleGrid);
return path;
}
private void findPath(int i, int j, int[][] obstacleGrid){
System.out.println("Current i and j is: " + i + ", " + j);
//end
if( i == 0 && j == 0){
System.out.println("Reach the start");
++path;
return;
}
// obstacle
if( i < 0 || j < 0 || obstacleGrid[i][j] == 1){
System.out.println("Dead way");
return;
}
// empty space
else{
// move left
System.out.println("Move leftward");
findPath( i, j-1, obstacleGrid);
// move top
System.out.println("Move upward");
findPath( i-1, j, obstacleGrid);
}
}
}For some reasons, it could pass the tests when I click "run code", but it will fail in submission with same input and different output.
Currently I am not sure what happens here.