Alright so i was implementing a solution of a problem which started of by giving you a (n,n) grid. It required me to to start at (1,1), visit certain points in the grid, marked as * and then finally proceed to (n,n). The size of the grid is guaranteed to be not more then 15 and the number of points to visit , * is guaranteed to be >=0 and <=n-2. The start and end points are always empty. There are certain obstacles , # where I cannot step on. Also, if i have visited a point before reaching a certain *, i can go through it again after collecting *.
Here is what my solution does. I made a datastructure called 'Node' which has 2 integer datatypes (x,y). It's basically a tuple.
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
While taking in the grid, i maintain a Set which stores the coordinates of '*' in the grid.
Set<Node> points=new HashSet<Node>();
I maintain a grid array and also a distance array
char [][]
int distances [][]
Now what i do is, i apply BFS as (1,1) as source. As soon as i encounter any '*' ( Which i believe will be the closest because BFS provides us with the shortest path in an unweighted graph ), I remove it from the Set.
Now i apply BFS again where my source becomes the last coordinate of '*' found. Everytime, i refresh the distance array since my source coordinate has changed. For the grid array, i refresh the paths marked as 'V' (visited) for the previous iteration.
This entire process continues until i reach the last '*'. BTW if my BFS returns -1, the program prints '-1' and quits.
Now if I have successfully reached all '' in the shortest possible way(i guess?), i set the (n,n) coordinate in the Grid as '' and apply BFS one last time. This way i get to the final point.
Now my solution seemd to be failing somewhere. Have gone wrong somewhere? Is my concept wrong? Does this 'greedy' approach fail? Getting the shortest path between all '*' checkpoints should eventually get me the shortest path IMO.
I looked around and saw this this problem is similar to the Travelling Salesman problem and also solvable by Dynamic Programming and DFS mix or A* algorithm.I have no clue how though. Someone even said dijkstra between each * but according to my knowledge, in an unweighted graph, Dijktra and BFS work the same. I just want to know why this BFS solution fails
Finally, Here is my code:
import java.io.*;
import java.util.*;
/**
* Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
*/
//ADD PUBLIC FOR CF,TC
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
class N1
{
//Datastructures and Datatypes used
static char grid[][];
static int distances[][];
static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
static int dx[]={1,-1,0,0};
static int dy[]={0,0,-1,1};
static Set<Node> points=new HashSet<Node>();
static int flag=1;
public static void main(String[] args) throws IOException
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();//testcases
for(int ixx=0;ixx<t;ixx++)
{
flag=1;
r=sc.nextInt();
if(r==1)
{
sc.next();//Taking in '.' basically
System.out.println("0");//Already there
continue;
}
c=r;//Rows guarenteed to be same as rows. It a nxn grid
grid=new char[r][c];
distances=new int[r][c];
points.clear();
for(int i=0;i<r;i++)
{
char[]x1=sc.next().toCharArray();
for(int j=0;j<c;j++)
{
grid[i][j]=x1[j];
if(x1[j]=='*')
{
points.add(new Node(i,j));
}
}
}//built grid
s1=s2=0;
distances[s1][s2]=0;//for 0,0
int ansd=0;
while(!points.isEmpty())
{
for(int i=0;i<r;i++)
{
for (int j = 0; j < c; j++)
{
distances[i][j]=0;
if(grid[i][j]=='V')//Visited
{
grid[i][j]='.';
}
}
}
distances[s1][s2]=0;
int dis=BFS();
if(dis!=-1)
{
ansd += dis;//Adding on (minimum?) distaces
//System.out.println("CURR DIS: "+ansd);
}
else
{
System.out.println("-1");
flag = 0;
break;
}
}
if(flag==1)
{
for(int i11=0;i11<r;i11++)
{
for(int j1=0;j1<c;j1++)
{
if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
{
grid[i11][j1]='.';
}
distances[i11][j1]=0;
}
}
f1=r-1;f2=c-1;
grid[f1][f2]='*';
int x=BFS();
if(x!=-1)
{
System.out.println((ansd+x));//Final distance
}
else
{
System.out.println("-1");//Not possible
}
}
}
}
public static int BFS()
{
// Printing current grid correctly according to concept
System.out.println("SOURCE IS:"+(s1+1)+","+(s2+1));
for(int i2=0;i2<r;i2++)
{
for (int j1 = 0; j1 < c; j1++)
{
{
System.out.print(grid[i2][j1]);
}
}
System.out.println();
}
Queue<Node>q=new LinkedList<Node>();
q.add(new Node(s1,s2));
while(!q.isEmpty())
{
Node p=q.poll();
for(int i=0;i<4;i++)
{
if(((p.x+dx[i]>=0)&&(p.x+dx[i]<r))&&((p.y+dy[i]>=0)&&(p.y+dy[i]<c))&&(grid[p.x+dx[i]][p.y+dy[i]]!='#'))
{//If point is in range
int cx,cy;
cx=p.x+dx[i];
cy=p.y+dy[i];
distances[cx][cy]=distances[p.x][p.y]+1;//Distances
if(grid[cx][cy]=='*')//destination
{
for(Node rm:points)// finding the node and removing it
{
if(rm.x==cx&&rm.y==cy)
{
points.remove(rm);
break;
}
}
grid[cx][cy]='.';//It i walkable again
s1=cx;s2=cy;//next source set
return distances[cx][cy];
}
else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
{
grid[cx][cy]='V';//Adding to visited
q.add(new Node(cx,cy));
}
}
}
}
return -1;
}
}
Here is my code in action for a few testcases. Gives the correct answer:
JAVA: http://ideone.com/qoE859
C++ : http://ideone.com/gsCSSL
Here is where my code fails: http://www.codechef.com/status/N1,bholagabbar
Your idea is wrong. I haven't read the code because what you describe will fail even if implemented perfectly.
Consider something like this:
x....
.....
..***
....*
*...*
You will traverse the maze like this:
x....
.....
..123
....4
*...5
Then go from 5 to the bottom-left * and back to 5, taking 16 steps. This however:
x....
.....
..234
....5
1...6
Takes 12 steps.
The correct solution to the problem involves brute force. Generate all permutations of the * positions, visit them in the order given by the permutation and take the minimum.
13! is rather large though, so this might not be fast enough. There is a faster solution by dynamic programming in O(2^k), similar to the Travelling Salesman Dynamic Programming Solution (also here).
I don't have time to talk about the solution much right now. If you have questions about it, feel free to ask another question and I'm sure someone will chime in (or leave this one open).