Given the starting point in a maze, you are to find and mark a path out of the m
ID: 669529 • Letter: G
Question
Given the starting point in a maze, you are to find and mark a path out of the maze which is represented by a 20x20 array of 1s (representing hedges) and 0s (representing the foot-paths). There is only one exit from the maze (represented by E). You may move vertically or horizontally in any direction that contains a 0; you may not move into a square with a 1. If you move into the square with an E, you have exited the maze. If you are in a square with 1s on three sides, you must go back the way you came and try another path. You may not move diagonally. For this program, use a single linked list only.
Program Requirements
Following are the requirements for this program:
§ Your program should use single linked list.
Input of program: Input is a 20x20 array of characters (1s, 0s, and E) from an ASCII text data file (maze.txt); for example:
E0001110000000100100
11100011101110001111
11111000101000111000
00001110101100010010
01011000101111000110
00001110000110011110
11011100110110111000
00011110110111111101
01011011110110100001
01000000000110110111
11011011010010000000
01010010011000101011
01111000101110101110
00001110000111011001
01101011101101000011
11000110100111011010
01110000100100110011
11010111110110000000
01110100011000111110
00011001000011100010
Each data line consists of one row of maze. Starting points (i.e. a row, column pair) in the maze will be input from the keyboard.
Output of program: Echo print the maze complete with numbered rows and columns prior to asking the user for their starting point. For each entry into the maze, print the complete maze with an S in the starting point followed by the words ‘I am free’ if you have found a path out of the maze or the words ‘Help, I am trapped’ if you cannot. Your output could be in two formats:
Print the path (by using a series of pluses (+)) you took through the maze should one be found, OR Print the path as a single linked list
Explanation / Answer
import java.io.*;
import java.util.*;
class cell {
int x;
int y;
cell parent;
char id;
int ID;
boolean reachable;
int g;
int h;
int f;
boolean inque;
boolean inarl;
public cell(int m,int n){
x = m;
y = n;
parent = null;
g=0;
h=0;
f=0;
ID=0;
inque=false;
inarl=false;
}
}
class PQtest {
PriorityQueue<cell> pq=new PriorityQueue<cell>(100,new Comparator<cell>() {
public int compare(cell c1,cell c2){
if (c1.f == c2.f) {
if (c1.ID > c2.ID)
return 1;
else
return -1;
}
else{
if (c1.f > c2.f)
return 1;
else
return -1;
}
}
});
}
class maze {
PQtest pqt=new PQtest();
// Linklist
ArrayList<cell> store = new ArrayList<cell>();
cell[][] Maze;
int maxsize=0;
int max_size = 0;
void drawMaze(int n,int m){
Maze=new cell[n][m];
max_size = n;
maxsize = m;
}
int j=0;
void fillMaze(String ch,int n){
if (j==maxsize)
j=0;
if (Maze[n][j]==null){
cell c=new cell(n,j);
c.id = 'i';
if (ch.equals("0"))
c.reachable=true;
else
c.reachable=false;
Maze[n][j]=c;
}
j++;
}
void updatefh(cell c1,int j1,int j2){
c1.h = 10*(Math.abs(c1.x-j1)+Math.abs(c1.y-j2));
if (c1.parent!=null){
c1.g = c1.parent.g+10;
}
c1.f = c1.g + c1.h;
}
void findneighbour(cell c,int j1,int j2){
cell c1;
int xx=c.x;
int yy=c.y;
if (c.y+1 < maxsize){
yy++;
c1 = Maze[xx][yy];
if (c1.reachable==true && c1.inque==false && c1.inarl==false){
c1.parent = c;
updatefh(c1,j1,j2);
c1.ID = c1.g+4;
pqt.pq.add(c1);
c1.inque=true;
}
yy--;
}
if (c.x+1 < max_size){
xx++;
c1 = Maze[xx][yy];
if (c1.reachable==true && c1.inque==false && c1.inarl==false){
c1.parent = c;
updatefh(c1,j1,j2);
c1.ID = c1.g+3;
pqt.pq.add(c1);
c1.inque=true;
}
xx--;
}
if (c.x-1 >= 0){
xx--;
c1 = Maze[xx][yy];
if (c1.reachable==true && c1.inque==false && c1.inarl==false){
c1.parent = c;
updatefh(c1,j1,j2);
c1.ID = c1.g+2;
pqt.pq.add(c1);
c1.inque=true;
}
xx++;
}
if (c.y-1 >= 0){
yy--;
c1 = Maze[xx][yy];
if (c1.reachable==true && c1.inque==false && c1.inarl==false){
c1.parent = c;
updatefh(c1,j1,j2);
c1.ID = c1.g+4;
pqt.pq.add(c1);
c1.inque=true;
}
yy++;
}
}
boolean findpath(int i1,int i2,int j1,int j2){
updatefh(Maze[i1][i2],j1,j2);
cell c = Maze[i1][i2];
pqt.pq.add(c);
c.inque=true;
cell cll = pqt.pq.poll();
while (cll.id!='E'){
findneighbour(cll,j1,j2);
store.add(cll);
cll.inarl = true;
if (pqt.pq.size()!=0){
cll = pqt.pq.poll();
}
else {
System.out.println("NO PATH EXIST BETWEEN "+"("+i1+" , "+i2+")"+" and "+"("+j1+" , "+j2+")");
return false;
}
}
System.out.println("SUCCESSFULLY PATH FOUND BETWEEN "+"("+i1+" , "+i2+")"+" and "+"("+j1+" , "+j2+")");
System.out.println(" ");
cll = Maze[j1][j2];
System.out.print("("+cll.x+","+cll.y+")"+" <--- ");
while (cll.parent.id!='S'){
cll = cll.parent;
System.out.print("("+cll.x+","+cll.y+")"+" <--- ");
}
System.out.println("("+cll.parent.x+","+cll.parent.y+")");
return true;
}
}
class run{
public static void main(String[] args) throws IOException{
InputStreamReader sr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(sr);
System.out.println("Enter The File Name Containing The Maze");
String ss = br.readLine();
StringTokenizer st;
maze mz=new maze();
Scanner sc = new Scanner(System.in);
try{
BufferedReader filereader=new BufferedReader(new FileReader(ss));
mz.drawMaze(20,20);
int i=0; String ch;
String Read = filereader.readLine();
while (Read!=null){
st = new StringTokenizer(Read);
while (st.hasMoreTokens()){
ch = st.nextToken();
mz.fillMaze(ch,i);
}
i++;
Read=filereader.readLine();
}
cell c2=new cell(19,19);
c2.ID = 0;
c2.id = 'E';
c2.reachable = true;
mz.Maze[19][19] = c2;
for (i = 19; i >= 0; i--){
for (int j = 19; j >= 0; j--){
if (mz.Maze[i][j].id == 'E')
System.out.print("E ");
else if (mz.Maze[i][j].reachable == true)
System.out.print("0 ");
else
System.out.print("1 ");
}
System.out.println();
}
System.out.println("Enter Starting co-ordinates (x,y) separated by space : ");
int start_x = sc.nextInt() - 1;
int start_y = sc.nextInt() - 1;
cell c1=new cell(start_x,start_y);
c1.ID = 0;
c1.id = 'S';
c1.reachable = true;
mz.Maze[start_x][start_y] = c1;
mz.findpath(start_x,start_y,19,19);
}catch(FileNotFoundException e){ System.out.println("there is no such file"); }
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.