Advertisement
fensa08

Untitled

Dec 29th, 2019
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.33 KB | None | 0 0
  1. import java.util.Hashtable;
  2. import java.util.LinkedList;
  3. import java.util.Scanner;
  4. import java.util.Stack;
  5.  
  6.  
  7. public class Lavirint {
  8.  
  9.  
  10. Graph graph;
  11. int start;
  12. int end;
  13. Hashtable<Integer, String> hash;
  14. Hashtable<String, Integer> rehash;
  15.  
  16. Lavirint() {
  17. hash = new Hashtable<>();
  18. rehash = new Hashtable<>();
  19. }
  20.  
  21. void createGraph(int rows, int columns, String [] input) {
  22.  
  23. int numNodes = 0;
  24. String key;
  25. GraphNode nodes[] = new GraphNode[rows * columns];
  26.  
  27. for (int i=0; i < rows; ++i) {
  28. for (int j=0; j < columns; ++j) {
  29. if (input[i].charAt(j) != '#') {
  30. key = i + "," + j;
  31. hash.put(numNodes,key);
  32. rehash.put(key, numNodes);
  33. nodes[numNodes] = new GraphNode(numNodes, key);
  34. if (input[i].charAt(j) == 'S')
  35. start = numNodes;
  36. if (input[i].charAt(j) == 'E')
  37. end = numNodes;
  38. ++numNodes;
  39. }
  40. }
  41. }
  42.  
  43. graph = new Graph(numNodes,nodes);
  44. int x;
  45. int y;
  46. for (int i=0; i < rows; ++i) {
  47. for (int j=0; j < columns; ++j) {
  48.  
  49. if (input[i].charAt(j) != '#') {
  50. if (input[i].charAt(j-1) != '#') {
  51. x = rehash.get(i + "," + j);
  52. y = rehash.get(i + "," + (j-1));
  53. graph.addEdge(x, y);
  54. }
  55.  
  56. if (input[i].charAt(j+1) != '#') {
  57. x = rehash.get(i + "," + j);
  58. y = rehash.get(i + "," + (j+1));
  59. graph.addEdge(x, y);
  60. }
  61.  
  62. if (input[i-1].charAt(j) != '#') {
  63. x = rehash.get(i + "," + j);
  64. y = rehash.get((i-1) + "," + j);
  65. graph.addEdge(x, y);
  66. }
  67.  
  68. if (input[i+1].charAt(j) != '#') {
  69. x = rehash.get(i + "," + j);
  70. y = rehash.get((i+1) + "," + j);
  71. graph.addEdge(x, y);
  72. }
  73.  
  74. }
  75.  
  76. }
  77. }
  78.  
  79. }
  80.  
  81. void findPath() {
  82. boolean visited[] = new boolean[graph.num_nodes];
  83. for (int i = 0; i < graph.num_nodes; i++)
  84. visited[i] = false;
  85. visited[start] = true;
  86. Stack<Integer> s = new Stack<Integer>();
  87. s.push(start);
  88.  
  89. GraphNode pom;
  90.  
  91. while (!s.isEmpty()&&s.peek() != end) {
  92. pom = graph.adjList[s.peek()];
  93. GraphNode tmp=null;
  94. for (int i = 0; i < pom.getNeighbors().size(); i++) {
  95. tmp = pom.getNeighbors().get(i);
  96. if (!visited[tmp.getIndex()])
  97. break;
  98. }
  99. if(tmp!=null&&!visited[tmp.getIndex()]){
  100. visited[tmp.getIndex()] = true;
  101. s.push(tmp.getIndex());
  102. }
  103. else
  104. s.pop();
  105. }
  106.  
  107. if(s.isEmpty())
  108. System.out.println("Nema reshenie");
  109. else{
  110. Stack<Integer> os = new Stack<Integer>();
  111. while(!s.isEmpty())
  112. os.push(s.pop());
  113. while(!os.isEmpty())
  114. System.out.println(hash.get(os.pop()));
  115. }
  116.  
  117. }
  118.  
  119. @Override
  120. public String toString() {
  121. return graph.toString();
  122. }
  123.  
  124. public static void main(String[] args) {
  125.  
  126. Scanner scan = new Scanner(System.in);
  127. Lavirint lavirint = new Lavirint();
  128. String line = scan.nextLine();
  129. String parts[] = line.split(",");
  130.  
  131. int rows = Integer.parseInt(parts[0]);
  132. int columns = Integer.parseInt(parts[1]);
  133.  
  134. String input[] = new String[rows];
  135.  
  136. for (int i=0; i < rows; ++i) {
  137. input[i] = scan.nextLine();
  138. }
  139.  
  140. lavirint.createGraph(rows, columns, input);
  141. lavirint.findPath();
  142. }
  143.  
  144.  
  145.  
  146. }
  147.  
  148. class GraphNode {
  149. private int index;//index (reden broj) na temeto vo grafot
  150. private String info;
  151. private LinkedList<GraphNode> neighbors;
  152.  
  153. public GraphNode(int index, String info) {
  154. this.index = index;
  155. this.info = info;
  156. neighbors = new LinkedList<GraphNode>();
  157. }
  158.  
  159. boolean containsNeighbor(GraphNode o){
  160. return neighbors.contains(o);
  161. }
  162.  
  163. void addNeighbor(GraphNode o){
  164. neighbors.add(o);
  165. }
  166.  
  167. void removeNeighbor(GraphNode o){
  168. if(neighbors.contains(o))
  169. neighbors.remove(o);
  170. }
  171.  
  172. @Override
  173. public boolean equals(Object obj) {
  174. @SuppressWarnings("unchecked")
  175. GraphNode pom = (GraphNode)obj;
  176. return (pom.info.equals(this.info));
  177. }
  178.  
  179. @Override
  180. public String toString() {
  181. return index + " " + info;
  182. }
  183.  
  184.  
  185. public int getIndex() {
  186. return index;
  187. }
  188.  
  189. public void setIndex(int index) {
  190. this.index = index;
  191. }
  192.  
  193. public String getInfo() {
  194. return info;
  195. }
  196.  
  197. public void setInfo(String info) {
  198. this.info = info;
  199. }
  200.  
  201. public LinkedList<GraphNode> getNeighbors() {
  202. return neighbors;
  203. }
  204.  
  205. public void setNeighbors(LinkedList<GraphNode> neighbors) {
  206. this.neighbors = neighbors;
  207. }
  208.  
  209. }
  210.  
  211. class Graph {
  212.  
  213. int num_nodes;
  214. GraphNode adjList[];
  215.  
  216. @SuppressWarnings("unchecked")
  217. public Graph(int num_nodes, GraphNode[] list) {
  218. this.num_nodes = num_nodes;
  219. adjList = new GraphNode[num_nodes];
  220. for (int i=0; i < num_nodes; ++i)
  221. adjList[i] = list[i];
  222. }
  223.  
  224. int adjacent(int x, int y) {
  225. // proveruva dali ima vrska od jazelot so
  226. // indeks x do jazelot so indeks y
  227. return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  228. }
  229.  
  230. void addEdge(int x, int y) {
  231. // dodava vrska od jazelot so indeks x do jazelot so indeks y
  232. if (!adjList[x].containsNeighbor(adjList[y])) {
  233. adjList[x].addNeighbor(adjList[y]);
  234. }
  235. if (!adjList[y].containsNeighbor(adjList[x])) {
  236. adjList[y].addNeighbor(adjList[x]);
  237. }
  238. }
  239.  
  240. void deleteEdge(int x, int y) {
  241. adjList[x].removeNeighbor(adjList[y]);
  242. adjList[y].removeNeighbor(adjList[x]);
  243. }
  244.  
  245. @Override
  246. public String toString() {
  247. String ret = new String();
  248. for(int i=0;i<this.num_nodes;i++)
  249. ret+=adjList[i]+"\n";
  250. return ret;
  251. }
  252.  
  253. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement