Advertisement
Guest User

Untitled

a guest
Jan 17th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.40 KB | None | 0 0
  1. package trasa;
  2.  
  3. import java.io.File;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileWriter;
  6. import java.io.IOException;
  7. import java.io.PrintWriter;
  8. import java.util.Comparator;
  9. import java.util.PriorityQueue;
  10. import java.util.Scanner;
  11.  
  12. public class Trasa {
  13.  
  14. public static void main(String[] args) throws FileNotFoundException, IOException {
  15. int n;
  16. int m;
  17. int startX, startY;
  18. int finishX, finishY;
  19.  
  20. Scanner input = new Scanner(new File("src/in.txt"));
  21. File output = new File("src/out.txt");
  22. FileWriter fWriter = new FileWriter(output);
  23. PrintWriter pWriter = new PrintWriter(fWriter);
  24.  
  25. n = input.nextInt();
  26. m = input.nextInt();
  27.  
  28. int[][] data = new int[n][m];
  29. boolean[][] visits = new boolean[n][m];
  30.  
  31. for (int i = 0; i < n; i++) {
  32. for (int j = 0; j < m; j++) {
  33. data[i][j] = input.nextInt();
  34. }
  35. }
  36.  
  37. startX = input.nextInt();
  38. startY = input.nextInt();
  39. finishX = input.nextInt();
  40. finishY = input.nextInt();
  41.  
  42. int[][] cost = new int[n][m];
  43. for (int i = 0; i < n; i++) {
  44. for (int j = 0; j < m; j++) {
  45. cost[i][j] = 0;
  46. //cost[i][j] = Integer.MAX_VALUE;
  47. }
  48. }
  49. cost[startX-1][startY-1] = Integer.MAX_VALUE;
  50. visits[startX-1][startY-1] = true;
  51.  
  52. int[][][] prev = new int[n][m][2];
  53. for (int i = 0; i < n; i++) {
  54. for (int j = 0; j < m; j++) {
  55. for (int k = 0; k < 2; k++) {
  56. prev[i][j][k] = -1;
  57. }
  58.  
  59. }
  60. }
  61.  
  62. Comparator<DataNode> comparator = new CostComparator();
  63. PriorityQueue<DataNode> costMin = new PriorityQueue<>(n * m, comparator);
  64.  
  65. int bufX = startX-1;
  66. int bufY = startY-1;
  67. int[] movingTab = new int[]{-1, 0, 1};
  68.  
  69. int buffMath;
  70. int movedBufX;
  71. int movedBufY;
  72.  
  73. // while (areAllTrue(visits) == false) {
  74. // for (int i = 0; i < 3; i++) {
  75. // for (int j = 0; j < 3; j++) {
  76. // if (movingTab[i] == 0 && movingTab[j] == 0) {
  77. // continue;
  78. // }
  79. // try {
  80. //
  81. // movedBufX = bufX + movingTab[i];
  82. // movedBufY = bufY + movingTab[j];
  83. //
  84. // if (visits[movedBufX][movedBufY] == false) {
  85. //
  86. // buffMath = (int) Math.pow((data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY]), 2);
  87. //
  88. // if (cost[movedBufX][movedBufY] > cost[bufX][bufY] + buffMath) {
  89. // cost[movedBufX][movedBufY] = (cost[bufX][bufY] + buffMath);
  90. //
  91. // prev[movedBufX][movedBufY][0] = bufX+1;
  92. // prev[movedBufX][movedBufY][1] = bufY+1;
  93. // costMin.add(new DataNode(cost[movedBufX][movedBufY], movedBufX, movedBufY));
  94. // }
  95. // }
  96. // } catch (Exception e) {
  97. // continue;
  98. // }
  99. // }
  100. // }
  101. //
  102. //
  103. // bufX = costMin.peek().corX;
  104. // bufY = costMin.peek().corY;
  105. // visits[costMin.peek().corX][costMin.peek().corY] = true;
  106. // costMin.remove();
  107. // }
  108. costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
  109. costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
  110. costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
  111. while (true) {
  112.  
  113. // visits[costMin.peek().corX][costMin.peek().corY] = true;
  114.  
  115. for (int i = 0; i < 3; i++) {
  116. for (int j = 0; j < 3; j++) {
  117. if (movingTab[i] == 0 && movingTab[j] == 0) {
  118. continue;
  119. }
  120. try {
  121.  
  122. movedBufX = bufX + movingTab[i];
  123. movedBufY = bufY + movingTab[j];
  124.  
  125. if(data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY] < 0){
  126. continue;
  127. }
  128.  
  129.  
  130.  
  131. buffMath = (int) Math.pow((data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY]), 2);
  132.  
  133. if (cost[movedBufX][movedBufY] <= cost[bufX][bufY] + buffMath) {
  134. cost[movedBufX][movedBufY] = (cost[bufX][bufY] + buffMath);
  135.  
  136. prev[movedBufX][movedBufY][0] = bufX+1;
  137. prev[movedBufX][movedBufY][1] = bufY+1;
  138. costMin.add(new DataNode(cost[movedBufX][movedBufY], movedBufX, movedBufY));
  139. }
  140.  
  141. } catch (Exception e) {
  142. continue;
  143. }
  144. }
  145. }
  146.  
  147.  
  148. bufX = costMin.peek().corX;
  149. bufY = costMin.peek().corY;
  150. visits[costMin.peek().corX][costMin.peek().corY] = true;
  151. costMin.remove();
  152. if(costMin.isEmpty() == true)break;
  153. }
  154. System.out.println(cost[finishX-1][finishY-1]);
  155.  
  156. }
  157.  
  158. private static class DataNode<Integer> {
  159.  
  160. DataNode(int thecost, int x, int y) {
  161. cost = thecost;
  162. corX = x;
  163. corY = y;
  164. }
  165. int cost;
  166. int corX;
  167. int corY;
  168. }
  169.  
  170. private static class CostComparator implements Comparator<DataNode> {
  171.  
  172. @Override
  173. public int compare(DataNode t, DataNode t1) {
  174. if (t.cost < t1.cost) {
  175. return 1;
  176. }
  177. if (t.cost > t1.cost) {
  178. return -1;
  179. }
  180. return 0;
  181.  
  182. }
  183. }
  184.  
  185. public static boolean areAllTrue(boolean[][] tab) {
  186. for (boolean[] b : tab) {
  187. for (boolean c : b) {
  188. if (!c) {
  189. return false;
  190. }
  191. }
  192. }
  193. return true;
  194. }
  195.  
  196. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement