powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка про остров
25 сообщений из 421, страница 4 из 17
Задачка про остров
    #39924992
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кто захочет поразвлекаться, исходные данные в массиве, списком и графом
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
public class Hexagon {

    public static final int NUMBER_OF_SIDES = 6;
    private int height;
    private String status;

    // индексы ребер
    //   1 /\ 2
    //  0 |  | 3
    //   5 \/ 4
    private Hexagon[] hexagonSides = new Hexagon[NUMBER_OF_SIDES];

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public void setHexagonSides(Hexagon[] hexagonSides) {
        this.hexagonSides = hexagonSides;
    }

    public Hexagon getHexagonSide(int side) {
        return hexagonSides[side];
    }

    public void setHexagonSide(int side, Hexagon hexagon) {
        this.hexagonSides[side] = hexagon;
    }

    public String getStatus() {
        return status;
    }

    public void setStatus(String status) {
        this.status = status;
    }

    public Hexagon(int height) {
        this.height = height;
    }

    @Override
    public String toString() {
        return Integer.toString(this.height);
    }
}



Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        //   1 /\ 2
        //  0 |  | 3
        //   5 \/ 4

        //         / \ / \ / \                    / \ / \ / \
        //        | 0 | 1 | 2 |                  | 1 | 4 | 3 |
        //       / \ / \ / \ / \                / \ / \ / \ / \
        //      | 3 | 4 | 5 | 6 |              | 1 | 5 | 1 | 5 |
        //     / \ / \ / \ / \ / \            / \ / \ / \ / \ / \
        //    | 7 | 8 | 9 | 10| 11|          | 2 | 3 | 2 | 4 | 6 |
        //     \ / \ / \ / \ / \ /            \ / \ / \ / \ / \ /
        //      | 12| 13| 14| 15|              | 2 | 6 | 4 | 2 |
        //       \ / \ / \ / \ /                \ / \ / \ / \ /
        //        | 16| 17| 18|                  | 3 | 1 | 2 |
        //         \ / \ / \ /                    \ / \ / \ /

        int[][] array = new int[][] {
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 4, 3, 0},
                {0, 0, 1, 5, 1, 5, 0},
                {0, 2, 3, 2, 4, 6, 0},
                {0, 2, 6, 4, 2, 0, 0},
                {0, 3, 1, 2, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0}
        };

        // массив шестиугольников
        Hexagon[][] arrayHexagons = new Hexagon[array.length][array[0].length];
        // список шестиугольников
        ArrayList <Hexagon> listOfHexagons = new ArrayList<>(20);

        // заполняем массив и список, ссылки в массиве и списке на одни и те же шестиугольники
        for (int i = 0; i < array.length; i++ ) {
            for (int k = 0; k < array[i].length; k++) {
                if (array[i][k] > 0) {
                    arrayHexagons[i][k] = new Hexagon(array[i][k]);
                    listOfHexagons.add(arrayHexagons[i][k]);
                } else {
                    arrayHexagons[i][k] = null;
                }
            }
        }

        // записываем связи шестиугольников друг с другом
        for (int i = 1; i < array.length - 1; i++ ) {
            for (int k = 1; k < array[i].length - 1; k++) {
                if (array[i][k] > 0) {
                    arrayHexagons[i][k].setHexagonSides(new Hexagon[] {
                                    arrayHexagons[i][k-1], arrayHexagons[i-1][k], arrayHexagons[i-1][k+1],
                                    arrayHexagons[i][k+1], arrayHexagons[i+1][k], arrayHexagons[i+1][k-1] });
                }
            }
        }

        System.out.println(listOfHexagons);
        System.out.println("====================================");
        for (Hexagon[] h1: arrayHexagons) {
            for (Hexagon h2: h1) {
                if (h2 != null) {
                    System.out.print(h2 + " - ");
                    for (int i = 0; i < Hexagon.NUMBER_OF_SIDES; i++) {
                        System.out.print(h2.getHexagonSide(i) + ((i+1 < Hexagon.NUMBER_OF_SIDES) ? ", " : ""));
                    }
                    System.out.println();
                }
            }
        }
    }
}

...
Рейтинг: 0 / 0
Задачка про остров
    #39924994
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
автори вот опять же, как быстро считать площади дырок на каждом срезе.
Когда у тебя есть массив луж, посчитать мне кажется сравнительно легко. Перебираешь высоты всех хексов, которые лужу окружают, берешь высоту самого маленького (Скажем X).
V воды в луже единичного хекса = (X-высота этого хекса)*1 //*1 потому как площадь хекса равна условной единице. Повторить для всех хексов которые в этой луже (т.е. исключить подсписок, который будет после рекурсии - т.е. исключить вложенную лужу, бортики этой лужи сами исключатся, потому что они выше X).
...
Рейтинг: 0 / 0
Задачка про остров
    #39925048
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задачу можно решать по разному. Можно - как олимпиадную - такими деревянными матрциами и хардкодом топологии.

Давайте ее сведем хотя-бы к уровню постнаовки и решения на теории графов.

Есть моё предположение что детектирование мостов и связности упрощает
эту задачу. Опять-же для некого подмножества исходных данных.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925108
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

я их всего этого набора слов гед-то слышал только матрица и графы :) Разверни свой вариант.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925113
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
        int[][] array = new int[][] {
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 4, 3, 0},
                {0, 0, 1, 5, 1, 5, 0},
                {0, 2, 3, 2, 4, 6, 0},
                {0, 2, 6, 4, 2, 0, 0},
                {0, 3, 1, 2, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0}
        };



Я согласен помогать и задачки на графы - интересны но мне часто лень тратить своё время на пустяки.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925117
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тоже в сторонке постою, мне не то что лень, но с этими фокусами я мало знаком, а учить ради единоразового представления пятисотую по счету технологию, это только за деньги на работе.
Хотя что эт отакое посмотрю конечно, интересно же.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925123
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как будет угодно. Я вообще хотел поднять отдельный топик. В продолжение моих Java Graph Libraries поисковых вопросов.
Primary Goal : на посмотреть параллельные алгоритмы на графах (к сожалению еще не выбрал какие).
Secondary Goal : java, atomic, locks, не-блокирующие коллекции и структуры данных.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925134
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz

Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925137
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iOracleDev
mayton
Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz

Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то.

Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925155
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм. А оказалось ничего сложного осваивать не надо, осталось понять как каждой ноде вес присвоить.

http://www.webgraphviz.com

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
"aa"->"ab"
"aa"->"ba"
"aa"->"bb"
"ab"->"bb"
"ab"->"bc"
"ab"->"ac"
"ac"->"bc"
"ac"->"bd"
"ba"->"ca"
"ba"->"cb"
"ba"->"bb"
"bb"->"cb"
"bb"->"cc"
"bb"->"bc"
"bc"->"cc"
"bc"->"cd"
"bc"->"bd"
"bd"->"cd"
"bd"->"ce"
"ca"->"cb"
"cb"->"cc"
"cb"->"da"
"cb"->"db"
"cc"->"dc"
"cc"->"db"
"cc"->"cd"
"cd"->"de"
"cd"->"ce"
"cd"->"dc"
"da"->"db"
"da"->"ea"
"db"->"ea"
"db"->"eb"
"db"->"dc"
"dc"->"de"
"dc"->"eb"
"dc"->"ec"
"ea"->"eb"
"eb"->"ec"
"ec"->"de"
"de"->"ce"
"ca"->"da"
}

...
Рейтинг: 0 / 0
Задачка про остров
    #39925156
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Подправил 41 и 42ую связи "de"->"ce"
"ca"->"da"
Блин вот красивая картинка.

digraph G {
"aa"->"ab"
"aa"->"ba"
"aa"->"bb"
"ab"->"bb"
"ab"->"bc"
"ab"->"ac"
"ac"->"bc"
"ac"->"bd"
"ba"->"ca"
"ba"->"cb"
"ba"->"bb"
"bb"->"cb"
"bb"->"cc"
"bb"->"bc"
"bc"->"cc"
"bc"->"cd"
"bc"->"bd"
"bd"->"cd"
"bd"->"ce"
"ca"->"cb"
"cb"->"cc"
"cb"->"da"
"cb"->"db"
"cc"->"dc"
"cc"->"db"
"cc"->"cd"
"cd"->"de"
"cd"->"ce"
"cd"->"dc"
"da"->"db"
"da"->"ea"
"db"->"ea"
"db"->"eb"
"db"->"dc"
"dc"->"de"
"dc"->"eb"
"dc"->"ec"
"ea"->"eb"
"eb"->"ec"
"de"->"ec"
"ce"->"de"
"ca"->"da"
}
...
Рейтинг: 0 / 0
Задачка про остров
    #39925157
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
нули точно нужны? вся картинка слетит - будет почти от каждого узла в ноль стрелка
...
Рейтинг: 0 / 0
Задачка про остров
    #39925159
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник, я не вижу картинок с хостинга https://d.radikal.ru/

Пожалуйста перепость их куда-то в другое место.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925163
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сами напросились нуль добавлен.
digraph G {
"aa"->"ab"
"aa"->"ba"
"aa"->"bb"
"ab"->"bb"
"ab"->"bc"
"ab"->"ac"
"ac"->"bc"
"ac"->"bd"
"ba"->"ca"
"ba"->"cb"
"ba"->"bb"
"bb"->"cb"
"bb"->"cc"
"bb"->"bc"
"bc"->"cc"
"bc"->"cd"
"bc"->"bd"
"bd"->"cd"
"bd"->"ce"
"ca"->"cb"
"cb"->"cc"
"cb"->"da"
"cb"->"db"
"cc"->"dc"
"cc"->"db"
"cc"->"cd"
"cd"->"de"
"cd"->"ce"
"cd"->"dc"
"da"->"db"
"da"->"ea"
"db"->"ea"
"db"->"eb"
"db"->"dc"
"dc"->"de"
"dc"->"eb"
"dc"->"ec"
"ea"->"eb"
"eb"->"ec"
"de"->"ec"
"ce"->"de"
"ca"->"da"
"aa"->"null"
"ab"->"null"
"ac"->"null"
"ba"->"null"
"bd"->"null"
"ca"->"null"
"ce"->"null"
"da"->"null"
"de"->"null"
"ea"->"null"
"eb"->"null"
"ec"->"null"
}

https://jpegshare.net/][img=https://jpegshare.net/images/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg[/img]
...
Рейтинг: 0 / 0
Задачка про остров
    #39925164
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[quot АСУ ТПшник#22077547]Сами напросились нуль добавлен.
digraph G {
"aa"->"ab"
"aa"->"ba"
"aa"->"bb"
"ab"->"bb"
"ab"->"bc"
"ab"->"ac"
"ac"->"bc"
"ac"->"bd"
"ba"->"ca"
"ba"->"cb"
"ba"->"bb"
"bb"->"cb"
"bb"->"cc"
"bb"->"bc"
"bc"->"cc"
"bc"->"cd"
"bc"->"bd"
"bd"->"cd"
"bd"->"ce"
"ca"->"cb"
"cb"->"cc"
"cb"->"da"
"cb"->"db"
"cc"->"dc"
"cc"->"db"
"cc"->"cd"
"cd"->"de"
"cd"->"ce"
"cd"->"dc"
"da"->"db"
"da"->"ea"
"db"->"ea"
"db"->"eb"
"db"->"dc"
"dc"->"de"
"dc"->"eb"
"dc"->"ec"
"ea"->"eb"
"eb"->"ec"
"de"->"ec"
"ce"->"de"
"ca"->"da"
"aa"->"null"
"ab"->"null"
"ac"->"null"
"ba"->"null"
"bd"->"null"
"ca"->"null"
"ce"->"null"
"da"->"null"
"de"->"null"
"ea"->"null"
"eb"->"null"
"ec"->"null"
}

посоветуйте такой жу удобный как радикал картинкохранилище без регистраций и прочего...
https://jpegshare.net/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg.html
...
Рейтинг: 0 / 0
Задачка про остров
    #39925167
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Увы увы. Либо амазон либо гуглдрайв. Последник шарится через веб или нет я не помню.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925173
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии.

Не любые плитки могут сложиться также как шестигранники, да и проблем особых нет, я забил константой количество граней, но можно сделать инициализацию массива граней на требуемую размерность и работай себе с любым количеством граней. Другой вопрос в каком формате загонять тестовые данные, для простого примера с обычного плоского массива (который ты сам и предложил))) высот самый оптимальный вариант, сложный пример желательно в чем то рисовать, скидывать в файл и засасывать файл в свою структуру для обсчета. В рисовалках подобных вещей не силен, тем более в их сопряжении с жавой, вообще жавист у нас ты один))

PS: у нас пока вменяемого алгоритма нет даже для шестигранников.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925175
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник,

Ориентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой (путь по которому сливается вода с более высокой плитки), если смотреть со стороны нод то вес дуги для нод к примеру 3 и 9 будет для тройки 6 для девятки -6.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925182
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник
Поэтому слезно прошу - посмотрите на мой вариант.
Алгоритм один послойный. Тупой как пробка. Самое сложное - найти таки эти окружности, что опять же решается в двумерном пространстве.
На каждую лужу - заряжаем опять ровно этот же алгоритм в рекурсии, пока не дойдем до вариант - что луж в остатке нет.

Я же не просто так написал, закрашивание оно игтуитивно понятно было с самого начала.

Ты совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925185
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
авторТы совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная.
Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика.
Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925186
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
авторОриентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой
Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925189
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник
Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика.
Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать.

Количество воды не интересно. Вложенных бубликов может быть сколько угодно, ров это тоже лужа, внутри луж могут быть выступы, поэтому я и говорю, задача найти все сухие и все затопленные плитки весьма нетривиальная.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925192
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник
Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите.

Исходник для расчета я сделал немного выше, шестисвязный список Hexagon, к нему можно итератор приделать, чтобы можно было переходить с ноды на ноду, посмотреть высоту ноды и высоты соседних уже можно сейчас, дело только за алгоритмом, которого пока нет.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925195
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хммм... Еще раз подумайте над моим алгоритмом, все учтено. И сосуды и прочее. Режем по слоям - где нет замкнутой фигуры - вода польется куда то еще.
Ров уровня 0 - будет резать люой бублик и в него уходить будет вода. Кляксу в кляке нарисуйте, соедините их рвом, алгоритм все равно сжует это и не поперхнется - бублики будут рисоваться на срезе рва (т.е. самой низкой точки берега рва)). Если их нет замкнутых - ваша вода утекла в море.
Чего уже проще - если фигура замкнута, никуда ничего из нее не потечет.
...
Рейтинг: 0 / 0
Задачка про остров
    #39925196
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
АСУ ТПшник,

Алгоритм поиска всех "замыканий" на уровне, в том числе множественных независимых есть?
...
Рейтинг: 0 / 0
25 сообщений из 421, страница 4 из 17
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка про остров
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]