In: Mechanical Engineering
********JAVA************
This program deals with graphs and path-finding within
them.
write a program which allows the user to enter multiple levels of a
text, consisting of a
'start', an 'exit', 'walls', and 'floors'. The letter S represents
the start. E is the exit. O (the letter 'oh') represents a
'floor' (meaning a path you can follow). X is a wall (meaning a
block you cannot pass).
The program will accept Standard Input (System.in), It is up to you
whether you wish to use an adjacency matrix or adjacency lists
(linked or array-based).
Ideally, the program will allow the user to find the 'fastest' path
through the maze. In this context, 'fastest'
means the fewest number of steps possible to get from the start to
the exit, without crossing a wall. Note: You
may only move North, South, East, West, Up, or Down (diagonal
travel is not allowed).
If no valid path exists, the program should say so. You may assume
'sane' input, and that a start and exit are
present (though there might not be a path connecting them). The
maps do not 'wrap' (i.e. you can't exit the left
edge to appear on the right edge), and you may not assume that a
floor will have a boundary of walls.
Specifically, the input will be as follows:
An integer for the width of the map (W)
An integer for the height (length) of the map (H)
An integer for the depth (number of layers) of the map (D)
D×H lines of W characters (from {X,O,S,E}), terminated with
newlines
For D layers, first the (H) lines of the top layer will be entered,
then the lines of the second-highest, etc.
In place of any line of W characters, it is legal to include an
entirely blank line (as such, any line will have W
characters followed by a \n, or consist solely of a \n. the code
must be able to ignore such blank lines, but
may never rely on their presence; an input might not have any blank
lines at all).
output should look like this:
Enter width: 8
Enter height: 5
Enter depth: 1
Enter maze below. Only rows of width 8 will be accepted.
XXXOOOOX
OXXXOXOE
OXXOOXXO
OSXOXXXO
XOOOXOOO
1. Solve suboptimally
2. Estimate optimal solution cost
3. Solve optimally
4. Enter new puzzle
5. Quit
:> 1
Not implemented. Use optimal instead.
1. Solve suboptimally
2. Estimate optimal solution cost
3. Solve optimally
4. Enter new puzzle
5. Quit
:> 3
Finding Solution...
Optimal Path Cost: 12
Optimal Path:
S E E N N E N N E E S E
#include<bits/stdc++.h>
using namespace std;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v)
{
cout << "\n Adjacency list of
vertex "
<< v
<< "\n head ";
for (auto x : adj[v])
cout << "-> " <<
x;
printf("\n");
}
}
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}