in Matrix A with 6 rows and 4 columns.
where '#' = blocked path and '.' = allowed path..
A = [[. . . #],
[# . # #],
[# . # .],
[# . . .],
[# . . .],
[# . . .]
]
How to find the number of steps needed to reach from top left to bottom left.I am able to traverse the matrix from top left to bottom right but unable to find the steps(which is 8 here)..But the code below I am getting answer as 12 which is wrong
My code is as below:
private static int numSteps(char[][] A) {
int row = A.length;
int col = A[0].length;
// directions array for row and column
// for north, south, east , west
int r[] = {-1, 1, 0, 0};
int c[] = {0, 0, 1, -1};
int steps = 0;
LinkedList<String> queuePos = new LinkedList<String>();
queuePos.add("0,0");
boolean[][] visited = new boolean[row][col];
while(!queuePos.isEmpty()) {
String pos = queuePos.poll();
int rowPos = Integer.parseInt(pos.split(",")[0]);
int colPos = Integer.parseInt(pos.split(",")[1]);
if(rowPos >= row - 1 && colPos>= col -1) {
return steps;
}
// looping for the four directions for surrounding nodes/neighbours
for(int i=0; i<r.length; i++) {
int newRow = rowPos + r[i];
int newCol = colPos + c[i];
if(newRow < 0 || newCol < 0 || newRow >= row || newCol >= col || A[newRow][newCol] == '#' || visited[newRow][newCol]) {
continue;
}
visited[newRow][newCol] = true;
queuePos.add(newRow + "," + newCol);
if(newRow == row - 1 && newCol == col -1) {
return steps;
}
}
steps+=1;
}
return steps;
}
I am not able to figure out where I should increase the "steps" variable by 1..Can anyone suggest the corrections here?
Advertisement
Answer
Since you are using BFS, in each step you should use all elements in queue, so you forgot the following lines of code in your while loop:
while(!queuePos.isEmpty()) {
int size = queuePos.size();
for (int idx = 0; idx < size; idx++) {
...
}
steps+=1;
}
Also, these lines of code are not necessary, you check them when you get a position from queue (queue.poll())
if(newRow == row - 1 && newCol == col -1) {
return steps;
}
So, slightly modified version is:
private static int numSteps(char[][] A) {
int row = A.length;
int col = A[0].length;
// directions array for row and column
// for north, south, east , west
int r[] = {-1, 1, 0, 0};
int c[] = {0, 0, 1, -1};
int steps = 0;
LinkedList<String> queuePos = new LinkedList<String>();
queuePos.add("0,0");
boolean[][] visited = new boolean[row][col];
while(!queuePos.isEmpty()) {
int size = queuePos.size();
for (int idx = 0; idx < size; idx++) {
String pos = queuePos.poll();
int rowPos = Integer.parseInt(pos.split(",")[0]);
int colPos = Integer.parseInt(pos.split(",")[1]);
if(rowPos >= row - 1 && colPos>= col -1) {
return steps;
}
// looping for the four directions for surrounding nodes/neighbours
for(int i=0; i<r.length; i++) {
int newRow = rowPos + r[i];
int newCol = colPos + c[i];
if(newRow < 0 || newCol < 0 || newRow >= row || newCol >= col || A[newRow][newCol] == '#' || visited[newRow][newCol]) {
continue;
}
visited[newRow][newCol] = true;
queuePos.add(newRow + "," + newCol);
}
}
steps+=1;
}
return steps;
}