AoC 2022 Day 12

package org.advent.of.code.y2022;

import java.util.*;


public class Line12 {

    private static class Dot {
        public int x, y, c;

        /***
         * Клетка на карте
         * @param x
         * @param y
         * @param c количество шагов до этой клетки
         */
        public Dot(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Dot dot)) return false;
            return x == dot.x && y == dot.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }


    public static void main(String[] args) {
//        data = test;
        solution();
    }

    private static final List<String> m = new ArrayList<>();
    private static final Queue<Dot> dots = new LinkedList<>();
    private static final Set<Dot> set = new HashSet<>();
    private static int xs, ys, xe, ye;
    private static int w = 0, h = 0;


    /***
     * Нужно: Пройти от S до E (S = a, E = z) по самому короткому пути.
     * Условие 1: a - минимальная высота, z - максимальная высота
     * Условие 2: Искать путь с минимальным перепадом высот.
     *
     * Задание 2: Длина пути из ближайшей пику низшей высоты.
     */
    private static void solution() {
        Scanner in = new Scanner(data);
        while (in.hasNextLine()) {
            int x = 0, y = h;
            String l = in.nextLine();
            w = l.length();
            m.add(l);
            h++;
            while (x < w) {
                if (isStart(x, y)) {
                    xs = x; // for task 1
                    ys = y; // for task 1
                    set(x, y, 'a');
                }
                if (isEnd(x, y)) {
//                    xe = x; // for task 1
//                    ye = y; // for task 1
                    xs = x; // for task 2
                    ys = y; // for task 2
                    set(x, y, 'z');
                }
                x++;
            }
        }

        dots.add(new Dot(xs, ys, 0));

        while (!dots.isEmpty()) {
            Dot d = dots.poll();

            if (set.contains(d))
                continue;
            set.add(d);

//            if (d.x == xe && d.y == ye) { // for task 1
            if (get(d.x, d.y) == 'a') { // for task 2
                System.out.println(d.c);
                break;
            }

            int[] dx = {1, 0, -1, 0};
            int[] dy = {0, 1, 0, -1};
            for (int i = 0; i < 4; i++) {
                int xn = d.x + dx[i], yn = d.y + dy[i];
                if (xn >= 0 && yn >= 0 && xn < w && yn < h
//                        && get(xn, yn) <= get(d.x, d.y) + 1) // for task 1
                        && get(xn, yn) >= get(d.x, d.y) - 1) // for task 2
                    dots.add(new Dot(xn, yn, d.c + 1));
            }
        }
    }


    private static char get(int x, int y) {
        if (x < 0 || y < 0 || x > w - 1 || y > h - 1) return '.';
        return m.get(y).charAt(x);
    }


    private static void set(int x, int y, char c) {
        char[] l = m.get(y).toCharArray();
        l[x] = c;
        m.set(y, String.valueOf(l));
    }


    private static boolean isStart(int x, int y) {
        return get(x, y) == 'S';
    }


    private static boolean isEnd(int x, int y) {
        return get(x, y) == 'E';
    }


    private static String test = """
            Sabqponm
            abcryxxl
            accszExk
            acctuvwj
            abdefghi
            """;


    private static String data = """
            abaaaaaccccccccccccccccccaaaaaaaaaaaaaccccaaaaaaaccccccccccccccccccccccccccccaaaaaa
            abaaaaaaccaaaacccccccccccaaaaaaaaacaaaacaaaaaaaaaacccccccccccccccccccccccccccaaaaaa
            abaaaaaacaaaaaccccccccccaaaaaaaaaaaaaaacaaaaaaaaaacccccccccccccaacccccccccccccaaaaa
            abaaaaaacaaaaaacccccccccaaaaaaaaaaaaaaccaaacaaaccccccccccccccccaacccccccccccccccaaa
            abccaaaccaaaaaacccaaaaccaaaaaaaaaaaaaccccaacaaacccccccccaacaccccacccccccccccccccaaa
            abcccccccaaaaaccccaaaacccccaaaaacccaaaccaaaaaaccccccccccaaaaccccccccccccccccccccaac
            abcccccccccaaaccccaaaacccccaaaaacccccccccaaaaaccccccccccklllllccccccccccccccccccccc
            abcccccccccccccccccaaccccccccaaccccccccaaaaaaaccccccccckklllllllcccccddccccaacccccc
            abaccccccccccccccccccccccccccaaccccccccaaaaaaaaccccccckkkklslllllcccddddddaaacccccc
            abacccccccccccccccccccccccccccccccaaaccaaaaaaaaccccccckkkssssslllllcddddddddacccccc
            abaccccccccccccccccccccccccccccccccaaaaccaaacaccccccckkksssssssslllmmmmmdddddaacccc
            abcccccccccccccccaaacccccccccccccaaaaaaccaacccccccccckkkssssusssslmmmmmmmdddddacccc
            abcccccccaaccccaaaaacccccccccccccaaaaaccccccaaaaaccckkkrssuuuussssqmmmmmmmmdddccccc
            abcccccccaaccccaaaaaacccccccaaccccaaaaacccccaaaaacckkkkrruuuuuussqqqqqqmmmmdddccccc
            abccccaaaaaaaacaaaaaacccccccaaaaccaaccaccccaaaaaacjkkkrrruuuxuuusqqqqqqqmmmmeeccccc
            abcaaaaaaaaaaacaaaaaccccccaaaaaacccccaaccccaaaaajjjjrrrrruuuxxuvvvvvvvqqqmmmeeccccc
            abcaacccaaaaccccaaaaaaacccaaaaacccacaaaccccaaaajjjjrrrrruuuxxxxvvvvvvvqqqmmeeeccccc
            abaaaaccaaaaacccccccaaaccccaaaaacaaaaaaaacccaajjjjrrrrtuuuuxxxyvyyyvvvqqqnneeeccccc
            abaaaaaaaaaaacccaaaaaaaccccaacaacaaaaaaaacccccjjjrrrttttuxxxxxyyyyyvvvqqnnneeeccccc
            abaaaaaaaccaacccaaaaaaaaacccccccccaaaaaaccccccjjjrrrtttxxxxxxxyyyyyvvvqqnnneeeccccc
            SbaaaaaacccccccccaaaaaaaaaccccccccaaaaacccccccjjjrrrtttxxxEzzzzyyyvvrrrnnneeecccccc
            abaaaaacccccccccccaaaaaaacccccccccaaaaaaccccccjjjqqqtttxxxxxyyyyyvvvrrrnnneeecccccc
            abaaacccccccccccaaaaaaaccaaccccccccccaaccaaaaajjjqqqttttxxxxyyyyyyvvrrrnnneeecccccc
            abaaacccccccccccaaaaaaaccaaacaaacccccccccaaaaajjjjqqqtttttxxyywyyyywvrrnnnfeecccccc
            abcaaacccccccaaaaaaaaaaacaaaaaaaccccccccaaaaaaciiiiqqqqtttxwyywwyywwwrrrnnfffcccccc
            abcccccccccccaaaaaaaaaaccaaaaaacccccccccaaaaaacciiiiqqqqttwwywwwwwwwwrrrnnfffcccccc
            abccccccccccccaaaaaacccaaaaaaaacccccccccaaaaaaccciiiiqqqttwwwwwswwwwrrrrnnfffcccccc
            abccccccccccccaaaaaacccaaaaaaaaacccccccccaaacccccciiiqqqtswwwwssssrrrrrroofffcccccc
            abccccccaaaaacaaaaaacccaaaaaaaaaaccccccccccccccccciiiqqqssswsssssssrrrrooofffaccccc
            abccccccaaaaacaaccaaccccccaaacaaacccccccccccccccccciiiqqssssssspoorrrooooofffaacccc
            abcccccaaaaaacccccccccccccaaacccccccccccccccccccccciiiqppssssspppooooooooffffaacccc
            abcccccaaaaaacccccccccccccaacccccccccccccccccccccccciipppppppppppoooooooffffaaccccc
            abcccccaaaaaaccccccccccccccccccccccccccccccccccccccciihppppppppgggggggggfffaaaccccc
            abccccccaaacccccccccccccccccccccccaccccccccccccccccchhhhpppppphggggggggggfaaaaccccc
            abaaaccccccccccccccccccccccaccccaaacccccccccccccccccchhhhhhhhhhgggggggggcaacccccccc
            abaaccaaaccaccccccccccccccaaacccaaacaacccaaaaacccccccchhhhhhhhhgaaccccccccccccccccc
            abaaacaaacaacccccccccaaaccaaaacaaaaaaaaccaaaaaccccccccchhhhhhaaaaacccccccccccccccca
            abaaaccaaaaaccccccccccaaacaaaaaaaacaaaaccaaaaaaccccccccccaaacccaaaacccccccccccaccca
            abcccaaaaaaccccccccccaaaaaaaaaaaaacaaaaccaaaaaaccccccccccaaaccccaaaccccccccccaaaaaa
            abcccaaaaaaaacccccccaaaaaaaaaaaaaaaaaccccaaaaaacccccccccccccccccccccccccccccccaaaaa
            abcccaacaaaaaccccccaaaaaaaaaaaaaaaaaaacccccaacccccccccccccccccccccccccccccccccaaaaa
            """;
}