Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.io.FileWriter;
- import java.util.*;
- /**
- * Created by Drys on 06.04.2016.
- */
- public class Run {
- int[] fringeVal = new int[6];
- Cell arr[][][][];
- public class XY {
- int x,y;
- public XY(int x, int y) {
- this.x = x;
- this.y = y;
- }
- public int getX() {
- return x;
- }
- public int getY() {
- return y;
- }
- }
- public class Pair implements Comparable{
- private int penalty;
- private Cell cell;
- public Pair(int penalty, Cell cell) {
- this.penalty = penalty;
- this.cell = cell;
- }
- public int getPenalty() {
- return penalty;
- }
- public Cell getCell() {
- return cell;
- }
- @Override
- public int compareTo(Object o) {
- return penalty - ((Pair)o).penalty;
- }
- }
- public class Cell {
- private boolean isCheked = false;
- private int val;
- private int i;
- private int j;
- private int g;
- private int orient;
- int shortWay;
- Stack<XY> stack = new Stack<>();
- private ArrayList<Cell> cells = new ArrayList<>();
- private ArrayList<Integer> travelCost = new ArrayList<>();
- Cell(int val, int i, int j, int g, int orient) {
- this.val = val;
- this.i = i;
- this.j = j;
- this.g = g;
- this.orient = orient;
- shortWay = 10002;
- stack.add(new XY(i ,j));
- }
- public void createNode() {
- if(orient == 0) {
- if(g == 0) {
- if(j != 0) {
- cells.add(arr[i][j - 1][3][0]);
- travelCost.add(Math.abs(arr[i][j][3][0].getVal() - fringeVal[3]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][4][1]);
- travelCost.add(Math.abs(arr[i - 1][j][4][1].getVal() - fringeVal[4]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][1][0]);
- travelCost.add(Math.abs(arr[i][j+1][1][0].getVal() - fringeVal[1]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][5][3]);
- travelCost.add(Math.abs(arr[i+1][j][5][3].getVal() - fringeVal[5]));
- }
- }
- if(g == 1) {
- if(j != 0) {
- cells.add(arr[i][j - 1][0][0]);
- travelCost.add(Math.abs(arr[i][j][0][0].getVal() - fringeVal[0]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][4][2]);
- travelCost.add(Math.abs(arr[i - 1][j][4][2].getVal() - fringeVal[4]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][2][0]);
- travelCost.add(Math.abs(arr[i][j+1][2][0].getVal() - fringeVal[2]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][5][0]);
- travelCost.add(Math.abs(arr[i+1][j][5][0].getVal() - fringeVal[5]));
- }
- }
- if (g == 2) {
- if(j != 0) {
- cells.add(arr[i][j - 1][1][0]);
- travelCost.add(Math.abs(arr[i][j][1][0].getVal() - fringeVal[1]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][4][3]);
- travelCost.add(Math.abs(arr[i - 1][j][4][3].getVal() - fringeVal[4]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][3][0]);
- travelCost.add(Math.abs(arr[i][j+1][3][0].getVal() - fringeVal[3]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][5][1]);
- travelCost.add(Math.abs(arr[i+1][j][5][1].getVal() - fringeVal[5]));
- }
- }
- if (g == 3) {
- if(j != 0) {
- cells.add(arr[i][j - 1][2][0]);
- travelCost.add(Math.abs(arr[i][j][2][0].getVal() - fringeVal[2]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][4][0]);
- travelCost.add(Math.abs(arr[i - 1][j][4][0].getVal() - fringeVal[4]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][0][0]);
- travelCost.add(Math.abs(arr[i][j+1][0][0].getVal() - fringeVal[0]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][5][0]);
- travelCost.add(Math.abs(arr[i+1][j][5][0].getVal() - fringeVal[5]));
- }
- }
- if (g == 4) {
- if(j != 0) {
- cells.add(arr[i][j - 1][2][1]);
- travelCost.add(Math.abs(arr[i][j][2][1].getVal() - fringeVal[2]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][1][2]);
- travelCost.add(Math.abs(arr[i - 1][j][1][2].getVal() - fringeVal[1]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][0][3]);
- travelCost.add(Math.abs(arr[i][j+1][0][3].getVal() - fringeVal[0]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][3][0]);
- travelCost.add(Math.abs(arr[i+1][j][3][0].getVal() - fringeVal[3]));
- }
- }
- if (g == 5) {
- if(j != 0) {
- cells.add(arr[i][j - 1][2][3]);
- travelCost.add(Math.abs(arr[i][j][2][3].getVal() - fringeVal[2]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][3][0]);
- travelCost.add(Math.abs(arr[i - 1][j][3][0].getVal() - fringeVal[3]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][0][1]);
- travelCost.add(Math.abs(arr[i][j+1][0][1].getVal() - fringeVal[0]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][1][2]);
- travelCost.add(Math.abs(arr[i+1][j][1][2].getVal() - fringeVal[1]));
- }
- }
- } else {
- if (orient == 1) {
- if(g == 0) {
- if(j != 0) {
- cells.add(arr[i][j - 1][5][0]);
- travelCost.add(Math.abs(arr[i][j][5][0].getVal() - fringeVal[5]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][3][1]);
- travelCost.add(Math.abs(arr[i - 1][j][3][1].getVal() - fringeVal[3]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][4][2]);
- travelCost.add(Math.abs(arr[i][j+1][4][2].getVal() - fringeVal[4]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][1][1]);
- travelCost.add(Math.abs(arr[i+1][j][1][1].getVal() - fringeVal[1]));
- }
- }
- if(g == 1) {
- if(j != 0) {
- cells.add(arr[i][j - 1][5][3]);
- travelCost.add(Math.abs(arr[i][j][5][3].getVal() - fringeVal[5]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][0][1]);
- travelCost.add(Math.abs(arr[i - 1][j][0][1].getVal() - fringeVal[0]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][4][3]);
- travelCost.add(Math.abs(arr[i][j+1][4][3].getVal() - fringeVal[4]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][2][1]);
- travelCost.add(Math.abs(arr[i+1][j][2][1].getVal() - fringeVal[2]));
- }
- }
- if (g == 2) {
- if(j != 0) {
- cells.add(arr[i][j - 1][5][2]);
- travelCost.add(Math.abs(arr[i][j][5][2].getVal() - fringeVal[1]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][1][1]);
- travelCost.add(Math.abs(arr[i - 1][j][1][1].getVal() - fringeVal[1]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][4][0]);
- travelCost.add(Math.abs(arr[i][j+1][4][0].getVal() - fringeVal[4]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][3][1]);
- travelCost.add(Math.abs(arr[i+1][j][3][1].getVal() - fringeVal[3]));
- }
- }
- if (g == 3) {
- if(j != 0) {
- cells.add(arr[i][j - 1][5][1]);
- travelCost.add(Math.abs(arr[i][j][5][1].getVal() - fringeVal[5]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][2][1]);
- travelCost.add(Math.abs(arr[i - 1][j][2][1].getVal() - fringeVal[2]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][4][1]);
- travelCost.add(Math.abs(arr[i][j+1][4][1].getVal() - fringeVal[1]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][0][1]);
- travelCost.add(Math.abs(arr[i+1][j][0][1].getVal() - fringeVal[0]));
- }
- }
- if (g == 4) {
- if(j != 0) {
- cells.add(arr[i][j - 1][3][1]);
- travelCost.add(Math.abs(arr[i][j][3][1].getVal() - fringeVal[3]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][2][2]);
- travelCost.add(Math.abs(arr[i - 1][j][2][2].getVal() - fringeVal[2]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][1][3]);
- travelCost.add(Math.abs(arr[i][j+1][1][3].getVal() - fringeVal[1]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][0][0]);
- travelCost.add(Math.abs(arr[i+1][j][0][0].getVal() - fringeVal[0]));
- }
- }
- if (g == 5) {
- if(j != 0) {
- cells.add(arr[i][j - 1][1][3]);
- travelCost.add(Math.abs(arr[i][j][1][3].getVal() - fringeVal[1]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][2][0]);
- travelCost.add(Math.abs(arr[i - 1][j][2][0].getVal() - fringeVal[2]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][3][1]);
- travelCost.add(Math.abs(arr[i][j+1][3][1].getVal() - fringeVal[3]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][0][2]);
- travelCost.add(Math.abs(arr[i+1][j][0][2].getVal() - fringeVal[0]));
- }
- }
- } else {
- if (orient == 2) {
- if(g == 0) {
- if(j != 0) {
- cells.add(arr[i][j - 1][1][2]);
- travelCost.add(Math.abs(arr[i][j][1][2].getVal() - fringeVal[1]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][5][1]);
- travelCost.add(Math.abs(arr[i - 1][j][5][1].getVal() - fringeVal[5]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][3][2]);
- travelCost.add(Math.abs(arr[i][j+1][3][2].getVal() - fringeVal[3]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][4][3]);
- travelCost.add(Math.abs(arr[i+1][j][4][3].getVal() - fringeVal[4]));
- }
- }
- if(g == 1) {
- if(j != 0) {
- cells.add(arr[i][j - 1][2][2]);
- travelCost.add(Math.abs(arr[i][j][2][2].getVal() - fringeVal[2]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][5][0]);
- travelCost.add(Math.abs(arr[i - 1][j][5][0].getVal() - fringeVal[5]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][0][2]);
- travelCost.add(Math.abs(arr[i][j+1][0][2].getVal() - fringeVal[0]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][4][0]);
- travelCost.add(Math.abs(arr[i+1][j][4][0].getVal() - fringeVal[4]));
- }
- }
- if (g == 2) {
- if(j != 0) {
- cells.add(arr[i][j - 1][3][2]);
- travelCost.add(Math.abs(arr[i][j][3][2].getVal() - fringeVal[3]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][5][3]);
- travelCost.add(Math.abs(arr[i - 1][j][5][3].getVal() - fringeVal[5]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][1][2]);
- travelCost.add(Math.abs(arr[i][j+1][1][2].getVal() - fringeVal[1]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][4][1]);
- travelCost.add(Math.abs(arr[i+1][j][4][1].getVal() - fringeVal[4]));
- }
- }
- if (g == 3) {
- if(j != 0) {
- cells.add(arr[i][j - 1][0][2]);
- travelCost.add(Math.abs(arr[i][j][0][2].getVal() - fringeVal[0]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][5][2]);
- travelCost.add(Math.abs(arr[i - 1][j][5][2].getVal() - fringeVal[5]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][2][2]);
- travelCost.add(Math.abs(arr[i][j+1][2][2].getVal() - fringeVal[2]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][4][2]);
- travelCost.add(Math.abs(arr[i+1][j][4][2].getVal() - fringeVal[4]));
- }
- }
- if (g == 4) {
- if(j != 0) {
- cells.add(arr[i][j - 1][0][1]);
- travelCost.add(Math.abs(arr[i][j][0][1].getVal() - fringeVal[0]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][3][2]);
- travelCost.add(Math.abs(arr[i - 1][j][3][2].getVal() - fringeVal[3]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][2][3]);
- travelCost.add(Math.abs(arr[i][j+1][2][3].getVal() - fringeVal[2]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][1][0]);
- travelCost.add(Math.abs(arr[i+1][j][1][0].getVal() - fringeVal[1]));
- }
- }
- if (g == 5) {
- if(j != 0) {
- cells.add(arr[i][j - 1][0][3]);
- travelCost.add(Math.abs(arr[i][j][0][3].getVal() - fringeVal[0]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][1][0]);
- travelCost.add(Math.abs(arr[i - 1][j][1][0].getVal() - fringeVal[1]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][2][1]);
- travelCost.add(Math.abs(arr[i][j+1][2][1].getVal() - fringeVal[2]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][3][2]);
- travelCost.add(Math.abs(arr[i+1][j][3][2].getVal() - fringeVal[3]));
- }
- }
- } else {
- if(g == 0) {
- if(j != 0) {
- cells.add(arr[i][j - 1][4][0]);
- travelCost.add(Math.abs(arr[i][j][4][0].getVal() - fringeVal[4]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][1][3]);
- travelCost.add(Math.abs(arr[i - 1][j][1][3].getVal() - fringeVal[1]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][5][2]);
- travelCost.add(Math.abs(arr[i][j+1][5][2].getVal() - fringeVal[5]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][3][3]);
- travelCost.add(Math.abs(arr[i+1][j][3][3].getVal() - fringeVal[3]));
- }
- }
- if(g == 1) {
- if(j != 0) {
- cells.add(arr[i][j - 1][4][1]);
- travelCost.add(Math.abs(arr[i][j][4][1].getVal() - fringeVal[4]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][2][3]);
- travelCost.add(Math.abs(arr[i - 1][j][2][3].getVal() - fringeVal[2]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][5][1]);
- travelCost.add(Math.abs(arr[i][j+1][5][1].getVal() - fringeVal[5]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][0][3]);
- travelCost.add(Math.abs(arr[i+1][j][0][3].getVal() - fringeVal[0]));
- }
- }
- if (g == 2) {
- if(j != 0) {
- cells.add(arr[i][j - 1][4][2]);
- travelCost.add(Math.abs(arr[i][j][4][2].getVal() - fringeVal[4]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][3][3]);
- travelCost.add(Math.abs(arr[i - 1][j][3][3].getVal() - fringeVal[3]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][5][0]);
- travelCost.add(Math.abs(arr[i][j+1][5][0].getVal() - fringeVal[5]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][1][3]);
- travelCost.add(Math.abs(arr[i+1][j][1][3].getVal() - fringeVal[1]));
- }
- }
- if (g == 3) {
- if(j != 0) {
- cells.add(arr[i][j - 1][4][3]);
- travelCost.add(Math.abs(arr[i][j][4][3].getVal() - fringeVal[4]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][0][3]);
- travelCost.add(Math.abs(arr[i - 1][j][0][3].getVal() - fringeVal[0]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][5][3]);
- travelCost.add(Math.abs(arr[i][j+1][5][3].getVal() - fringeVal[5]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][2][3]);
- travelCost.add(Math.abs(arr[i+1][j][2][3].getVal() - fringeVal[2]));
- }
- }
- if (g == 4) {
- if(j != 0) {
- cells.add(arr[i][j - 1][1][1]);
- travelCost.add(Math.abs(arr[i][j][1][1].getVal() - fringeVal[1]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][0][2]);
- travelCost.add(Math.abs(arr[i - 1][j][0][2].getVal() - fringeVal[0]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][3][3]);
- travelCost.add(Math.abs(arr[i][j+1][3][3].getVal() - fringeVal[3]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][2][0]);
- travelCost.add(Math.abs(arr[i+1][j][2][0].getVal() - fringeVal[2]));
- }
- }
- if (g == 5) {
- if(j != 0) {
- cells.add(arr[i][j - 1][3][3]);
- travelCost.add(Math.abs(arr[i][j][3][3].getVal() - fringeVal[3]));
- }
- if(i != 0) {
- cells.add(arr[i - 1][j][0][0]);
- travelCost.add(Math.abs(arr[i - 1][j][0][0].getVal() - fringeVal[0]));
- }
- if(j < arr[0].length - 1) {
- cells.add(arr[i][j+1][1][1]);
- travelCost.add(Math.abs(arr[i][j+1][1][1].getVal() - fringeVal[1]));
- }
- if(i < arr.length - 1) {
- cells.add(arr[i+1][j][2][2]);
- travelCost.add(Math.abs(arr[i+1][j][2][2].getVal() - fringeVal[2]));
- }
- }
- }
- }
- }
- }
- public boolean isCheked() {
- return isCheked;
- }
- public void setCheked(boolean cheked) {
- isCheked = cheked;
- }
- public int getVal() {
- return val;
- }
- }
- public static void main(String[] args) throws Exception {
- Run obj = new Run();
- obj.run(args);
- }
- public void run(String[] args) throws Exception {
- Scanner sc = new Scanner(new File("input.txt"));
- int n = sc.nextInt();
- int m = sc.nextInt();
- arr = new Cell[n][m][6][4];
- for (int j = 0; j < n; j++) {
- for (int i = 0; i < m; i++) {
- int value = sc.nextInt();
- for (int g = 0; g < 6; g++) {
- for (int orient = 0; orient < 4; orient++) {
- arr[i][j][g][orient] = new Cell(value, i, j, g,orient);
- }
- }
- }
- }
- for (int i = 0 ; i < 6; i++) {
- fringeVal[i] = sc.nextInt();
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- for (int g = 0; g < 6; g++) {
- for (int orient = 0; orient < 4; orient++) {
- arr[i][j][g][orient].createNode();
- }
- }
- }
- }
- int q = sc.nextInt() - 1;
- int w = sc.nextInt() - 1;
- arr[q][w][1][0].shortWay = 0;
- dejkstra(new PriorityQueue<>(Arrays.asList(new Pair(0,arr[q][w][1][0]))));
- int c = 0,d = 0;
- int a = sc.nextInt() - 1;
- int b = sc.nextInt() - 1;
- for(int i = 0; i < 6; i++){
- for(int j = 0; j < 4; j++){
- if(arr[a][b][i][j].shortWay < arr[a][b][c][d].shortWay) {
- c = i;
- d = j;
- }
- }
- }
- FileWriter fileWriter = new FileWriter(new File("output.txt"));
- fileWriter.write(arr[a][b][c][d].stack.size() + "\n");
- int h = arr[a][b][c][d].stack.size();
- for (int i = 0; i < h; i++) {
- XY x = arr[a][b][c][d].stack.pop();
- fileWriter.write((x.getX() + 1) + " " + (x.getY()+ 1) + "\n" );
- }
- fileWriter.close();
- }
- public void dejkstra(PriorityQueue<Pair> steps) {
- Cell cell = steps.remove().getCell();
- for(int i = 0; i < cell.cells.size(); i++) {
- if(!cell.cells.get(i).isCheked) {
- int path = cell.shortWay + cell.travelCost.get(i);
- if (cell.cells.get(i).shortWay >= path) {
- cell.cells.get(i).shortWay = path;
- cell.cells.get(i).stack = new Stack<>();
- cell.cells.get(i).stack.add(new XY( cell.cells.get(i).i, cell.cells.get(i).j));
- cell.cells.get(i).stack.addAll(cell.stack);
- Pair pair = new Pair(path,cell.cells.get(i));
- if(!steps.contains(pair)) {
- steps.add(pair);
- }
- }
- }
- }
- cell.setCheked(true);
- if(!steps.isEmpty())
- dejkstra(steps);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement