I'm stuck at the solution of a problem.
Problem => You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minimum number of moves to get to the goal.
Example =>
...
.X.
...
The starting position (0,0) so start in the top left corner. The goal is (1,2) The path is (0,0)->(0,2)->(1,2). It takes moves to reach the goal. Output = 2
Solution=> BFS using Queue.
But how BFS can get to the minimum path for example if there is more than one path exist between starting and ending point then how BFS can get to the minimum one ?
Here is my solution for the above problem. But it doesn't work.
class Pair{
int x,y;
Pair(int a,int b){x=a;y=b;}
}
class Result {
public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY)
{
int n=grid.get(0).length();
ArrayDeque<Pair> q=new ArrayDeque<Pair>();
Pair location[][]=new Pair[n][n];
char color[][]=new char[n][n];
//default color a mean it is neither in queue nor explore
//till now, b mean it is in queue, c means it already explore
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
color[i][j]='a';
}
}
q.addLast(new Pair(startX,startY));
int tempx,tempy,tempi,tempj;
while(!q.isEmpty()){
tempx=q.peekFirst().x;
tempy=q.peekFirst().y;
q.removeFirst();
color[tempx][tempy]='c';
tempj=tempy-1;
tempi=tempx;
//cheking unvisited node around -X axis
while(tempj>=0){
if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
break;
}
q.addLast(new Pair(tempi,tempj));
color[tempi][tempj]='b';
location[tempi][tempj]=new Pair(tempx,tempy);
tempj--;
}
//checking unvisited node around +X axis
tempi=tempx;
tempj=tempy+1;
while(tempj<n){
if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
break;
}
q.addLast(new Pair(tempi,tempj));
color[tempi][tempj]='b';
location[tempi][tempj]=new Pair(tempx,tempy);
tempj++;
}
//checking unvisited node around +Y axis
tempi=tempx-1;
tempj=tempy;
while(tempi>=0){
if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
break;
}
q.addLast(new Pair(tempi,tempj));
color[tempi][tempj]='b';
location[tempi][tempj]=new Pair(tempx,tempy);
tempi--;
}
checking unvisited node around -Y axis
tempi=tempx+1;
tempj=tempy;
while(tempi<n){
if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
break;
}
q.addLast(new Pair(tempi,tempj));
color[tempi][tempj]='b';
location[tempi][tempj]=new Pair(tempx,tempy);
tempi++;
}
}//end of main while
//for track the path
Stack<Pair> stack=new Stack<Pair>();
//If path doesn't exist
if(location[goalX][goalY]==null){
return -1;
}
boolean move=true;
stack.push(new Pair(goalX,goalY));
while(move){
tempi=stack.peek().x;
tempj=stack.peek().y;
stack.push(location[tempi][tempj]);
if(tempi==startX && tempj==startY){
move=false;
}
}
System.out.println(stack);
return stack.size()-2;
}
}
Here My algorithm only find the path. Not the minimum path. Can anyone suggest me how BFS finds the minimum path here and what should I change into my code ?
BFS finds the minimal path by concentric moving outward, so everything in round 1 is 1 away from start, all squares added there are then 2 away from start and so on. This means the basic idea of using BFS to find the path is good, unfortunately the implementation is a bit difficult and slow.
Another way of viewing it is to think about the grid as a graph, with all squares connected to all other squares up, down, left and right until they hit the edge or an obstacle.
A third way of thinking of it is like a flood fill, first round only start is filled, next round all that can be accessed from it is filled and so on.
The major thing is that you break when you see a b.
aabbaaaaaa
aabbbaaaaa
babbbaaaaa
babbbaaaaa
babbbaaaaa
babbbaaaaa
bbbbbaaaaa
bbbbbaaaaa
bCbbbAAAAA
cccccaaaaa
When processing the capital Cit stops because it is surrounded by bs and cs. And therefore you don't examine the As.
I have hacked the code a bit, note i'm not a java programmer ... my main problem when trying to solve it was timeouts. I believe this can be solved without the location array by recording how many generations of BFS we run, that should save a lot of memory and time.
class Pair{
int x,y;
Pair(int a,int b){x=a;y=b;}
public String toString() {
return "[" + x + "," + y + "]";
}
}
class Result {
/*
* Complete the 'minimumMoves' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. STRING_ARRAY grid
* 2. INTEGER startX
* 3. INTEGER startY
* 4. INTEGER goalX
* 5. INTEGER goalY
*/
public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {
if (startX==goalX&&startY==goalY)
return 0;
startX += 1;
startY += 1;
goalX += 1;
goalY += 1;
int n=grid.get(0).length();
Pair dirs[] = {new Pair(-1,0), new Pair(+1,0), new Pair(0,-1), new Pair(0,+1)};
ArrayDeque<Pair> q=new ArrayDeque<Pair>();
Pair location[][]=new Pair[n+2][n+2];
char color[][]=new char[n+2][n+2];
//default color a mean it is neither in queue nor explore
//till now, b mean it is in queue, c means it already explore
for(int i=0;i<n+2;i++){
for(int j=0;j<n+2;j++){
if (i == 0 || i == n+1 ||j == 0 || j == n+1 || // boarder
grid.get(i-1).charAt(j-1)!='.')
color[i][j]='x';
else
color[i][j]='a';
}
}
q.addLast(new Pair(startX,startY));
int tempx,tempy,tempi,tempj;
while(!q.isEmpty()){
tempx=q.peekFirst().x;
tempy=q.peekFirst().y;
q.removeFirst();
if(location[goalX][goalY]!=null){
System.out.println("Goal reached");
break;
}
color[tempx][tempy]='c';
for (Pair dir : dirs ) {
tempi=tempx;
tempj=tempy;
while(true){
tempi+=dir.x;
tempj+=dir.y;
if (color[tempi][tempj]=='x') { // includes boarder
break;
}
if (color[tempi][tempj]>='b') {
continue;
}
q.addLast(new Pair(tempi,tempj));
color[tempi][tempj]='b';
location[tempi][tempj]=new Pair(tempx,tempy);
}
}
// System.out.println(location[goalX][goalY]);
// for(int i = 1; i < n+1; i++) {
// for(int j = 1; j < n+1; j++) {
// System.out.printf("%c", color[i][j]);
// }
// System.out.println();
// }
}//end of main while
//for track the path
Stack<Pair> stack=new Stack<Pair>();
//If path doesn't exist
if(location[goalX][goalY]==null){
System.out.printf("Gaol not reached %d %d", goalX, goalY);
System.out.println();
for(int i = 1; i < n+1; i++) {
for(int j = 1; j < n+1; j++) {
System.out.printf("%s", location[i][j]);
}
System.out.println();
}
return -1;
}
boolean move=true;
int moves = 0;
tempi = goalX;
tempj = goalY;
while(move){
System.out.println(String.valueOf(tempi)+" "+ String.valueOf(tempj));
moves = moves +1;
Pair cur = location[tempi][tempj];
tempi=cur.x;
tempj=cur.y;
if(tempi==startX && tempj==startY){
move=false;
}
}
System.out.println(moves);
return moves;
}
}