Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package trasa;
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- import java.util.Scanner;
- public class Trasa {
- public static void main(String[] args) throws FileNotFoundException, IOException {
- int n;
- int m;
- int startX, startY;
- int finishX, finishY;
- Scanner input = new Scanner(new File("src/in.txt"));
- File output = new File("src/out.txt");
- FileWriter fWriter = new FileWriter(output);
- PrintWriter pWriter = new PrintWriter(fWriter);
- n = input.nextInt();
- m = input.nextInt();
- int[][] data = new int[n][m];
- boolean[][] visits = new boolean[n][m];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- data[i][j] = input.nextInt();
- }
- }
- startX = input.nextInt();
- startY = input.nextInt();
- finishX = input.nextInt();
- finishY = input.nextInt();
- int[][] cost = new int[n][m];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cost[i][j] = 0;
- //cost[i][j] = Integer.MAX_VALUE;
- }
- }
- cost[startX-1][startY-1] = Integer.MAX_VALUE;
- visits[startX-1][startY-1] = true;
- int[][][] prev = new int[n][m][2];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- for (int k = 0; k < 2; k++) {
- prev[i][j][k] = -1;
- }
- }
- }
- Comparator<DataNode> comparator = new CostComparator();
- PriorityQueue<DataNode> costMin = new PriorityQueue<>(n * m, comparator);
- int bufX = startX-1;
- int bufY = startY-1;
- int[] movingTab = new int[]{-1, 0, 1};
- int buffMath;
- int movedBufX;
- int movedBufY;
- // while (areAllTrue(visits) == false) {
- // for (int i = 0; i < 3; i++) {
- // for (int j = 0; j < 3; j++) {
- // if (movingTab[i] == 0 && movingTab[j] == 0) {
- // continue;
- // }
- // try {
- //
- // movedBufX = bufX + movingTab[i];
- // movedBufY = bufY + movingTab[j];
- //
- // if (visits[movedBufX][movedBufY] == false) {
- //
- // buffMath = (int) Math.pow((data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY]), 2);
- //
- // if (cost[movedBufX][movedBufY] > cost[bufX][bufY] + buffMath) {
- // cost[movedBufX][movedBufY] = (cost[bufX][bufY] + buffMath);
- //
- // prev[movedBufX][movedBufY][0] = bufX+1;
- // prev[movedBufX][movedBufY][1] = bufY+1;
- // costMin.add(new DataNode(cost[movedBufX][movedBufY], movedBufX, movedBufY));
- // }
- // }
- // } catch (Exception e) {
- // continue;
- // }
- // }
- // }
- //
- //
- // bufX = costMin.peek().corX;
- // bufY = costMin.peek().corY;
- // visits[costMin.peek().corX][costMin.peek().corY] = true;
- // costMin.remove();
- // }
- costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
- costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
- costMin.add(new DataNode(cost[bufX][bufY], bufX, bufY));
- while (true) {
- // visits[costMin.peek().corX][costMin.peek().corY] = true;
- for (int i = 0; i < 3; i++) {
- for (int j = 0; j < 3; j++) {
- if (movingTab[i] == 0 && movingTab[j] == 0) {
- continue;
- }
- try {
- movedBufX = bufX + movingTab[i];
- movedBufY = bufY + movingTab[j];
- if(data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY] < 0){
- continue;
- }
- buffMath = (int) Math.pow((data[bufX + movingTab[i]][bufY + movingTab[j]] - data[bufX][bufY]), 2);
- if (cost[movedBufX][movedBufY] <= cost[bufX][bufY] + buffMath) {
- cost[movedBufX][movedBufY] = (cost[bufX][bufY] + buffMath);
- prev[movedBufX][movedBufY][0] = bufX+1;
- prev[movedBufX][movedBufY][1] = bufY+1;
- costMin.add(new DataNode(cost[movedBufX][movedBufY], movedBufX, movedBufY));
- }
- } catch (Exception e) {
- continue;
- }
- }
- }
- bufX = costMin.peek().corX;
- bufY = costMin.peek().corY;
- visits[costMin.peek().corX][costMin.peek().corY] = true;
- costMin.remove();
- if(costMin.isEmpty() == true)break;
- }
- System.out.println(cost[finishX-1][finishY-1]);
- }
- private static class DataNode<Integer> {
- DataNode(int thecost, int x, int y) {
- cost = thecost;
- corX = x;
- corY = y;
- }
- int cost;
- int corX;
- int corY;
- }
- private static class CostComparator implements Comparator<DataNode> {
- @Override
- public int compare(DataNode t, DataNode t1) {
- if (t.cost < t1.cost) {
- return 1;
- }
- if (t.cost > t1.cost) {
- return -1;
- }
- return 0;
- }
- }
- public static boolean areAllTrue(boolean[][] tab) {
- for (boolean[] b : tab) {
- for (boolean c : b) {
- if (!c) {
- return false;
- }
- }
- }
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement