Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.90/29: Рейтинг темы: голосов - 29, средняя оценка - 4.90
1 / 1 / 0
Регистрация: 14.01.2018
Сообщений: 102

Волновой алгоритм

20.08.2018, 17:30. Показов 5805. Ответов 14

Студворк — интернет-сервис помощи студентам
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. В начальный момент времени в исследуемую область проникли несколько вирусов. Напишите программу, которая найдёт время заражения всей исследуемой прямоугольной области.

Некоторый тест решение не проходит, некое подобие волнового алгоритма правильно? И еще решение хоть чуточку правильно или нет?

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
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.Scanner;
import java.io.PrintWriter;
 
import java.util.*;
 
public class tasksOl {
 
    public static void main(String[] args) throws FileNotFoundException {
        new tasksOl().soluction();
    }
 
    void soluction() throws FileNotFoundException {
        Scanner in = new Scanner(new FileReader("INPUT.TXT"));
       PrintWriter out = new PrintWriter("OUTPUT.TXT");
        run(in, out);
    }
 
 
 
    void run(Scanner in, PrintWriter out){
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] mas = new int[n+2][m+2];
        int k = in.nextInt();
 
        ArrayList<Integer> list = new ArrayList<>();
        for(int i =0; i<k; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            mas[a][b] = 0;
            list.add(a*10+b);
        }
 
        int sub, dist;
        for(int i =1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                sub = Integer.MAX_VALUE;
                for(int x : list){
                    int a = x/10;
                    int b = x%10;
                    dist = Math.abs(a-i)+Math.abs(b-j);
                    if(sub>dist){
                        sub = dist;
                        mas[i][j]=sub;
                    }
              
                }
            }
 
        }
 
        int max = -1;
        for(int i =1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                if(mas[i][j]>max)
                    max = mas[i][j];
            }
        }
 
        out.println(max);
 
        in.close();
        out.close();
 
    }
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
20.08.2018, 17:30
Ответы с готовыми решениями:

Волновой алгоритм
Доброго времени суток. Нужно написать волновой алгоритм, для нахождения кратчайшего пути в лабиринте. Никак не могу найти пример на...

Волновой алгоритм не работает
Никак не могу разобраться с волновым алгоритмом. Волна &quot;плывет&quot; только в одну сторону. Тут все читал, Википедию смотрел. Где-то ошибка. Код...

Волновой алгоритм
Доброго времени суток. Нужно написать волновой алгоритм, для нахождения кратчайшего пути в лабиринте. Никак не могу найти пример на...

14
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
20.08.2018, 18:03
Цитата Сообщение от stupid_man Посмотреть сообщение
Некоторый тест решение не проходит
опять какой-то джавараш чтоли?

Добавлено через 40 секунд
Цитата Сообщение от stupid_man Посмотреть сообщение
И еще решение хоть чуточку правильно или нет?
если тест не проходит, значит неправильное, это же очевидно
0
1 / 1 / 0
Регистрация: 14.01.2018
Сообщений: 102
20.08.2018, 18:18  [ТС]
Цитата Сообщение от xoraxax Посмотреть сообщение
опять какой-то джавараш чтоли?
Нет, сайт для решения олимпиадных задач
Цитата Сообщение от xoraxax Посмотреть сообщение
если тест не проходит, значит неправильное, это же очевидно
Это понятно, вопрос заключался в том, что не так с решением и в правильном русле оно идет или нет
0
64 / 64 / 26
Регистрация: 07.01.2016
Сообщений: 374
21.08.2018, 01:13
все не так, и не в правильном русле
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
21.08.2018, 18:27
stupid_man, как вариант. Идея в том, что храним координаты зараженных клеток на предыдущем шаге. Проходимся по всем этим клеткам и запоминаем координаты зараженных клеток на текущем шаге. Цикл повторяется пока на текущем шаге была заражена хоть одна клетка. Переделаете под свои входные/ваходные данные:
Кликните здесь для просмотра всего текста
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class FillArea {
    public static void main(String[] args) {
        int[][] area = new int[5][5];
 
        List<Point> filled = new LinkedList<>();
        /*добавляем координаты зараженных областей*/
        filled.add(new Point(1, 4));
        filled.add(new Point(0, 0));
        filled.add(new Point(4, 4));
        init(area, filled);
 
        int step = 1;
        System.out.println("After init: ");
        print(area);
 
        do {
            step++;
            List<Point> lastField = filled;
            filled = new LinkedList<>();
            nextStep(area, lastField, filled, step);
            System.out.println("Step = " + step);
            print(area);
        } while (filled.size() != 0);
        System.out.println("Answer: " + (step - 1));
    }
 
    public static void init(int[][] area, List<Point> filled) {
        for (Point point : filled) {
            area[point.row][point.col] = 1;
        }
    }
 
    public static void print(int[][] area) {
        for (int[] row : area) {
            for (int element : row) {
                System.out.format("%5d", element);
            }
            System.out.println();
        }
    }
 
    public static void nextStep(int[][] area, List<Point> lastFilled, List<Point> filled, int step) {
        for (Point point : lastFilled) {
            int row = point.getRow();
            int col = point.getCol();
            if (row > 0 && area[row - 1][col] == 0) {
                area[row - 1][col] = step;
                filled.add(new Point(row - 1, col));
            }
            if (col > 0 && area[row][col - 1] == 0) {
                area[row][col - 1] = step;
                filled.add(new Point(row, col - 1));
            }
            if (row < area.length - 1 && area[row + 1][col] == 0) {
                area[row + 1][col] = step;
                filled.add(new Point(row + 1, col));
            }
            if (col < area[row].length - 1 && area[row][col + 1] == 0) {
                area[row][col + 1] = step;
                filled.add(new Point(row, col + 1));
            }
        }
    }
 
    private static class Point {
        private int row;
        private int col;
 
        Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
 
        int getRow() {
            return row;
        }
 
        int getCol() {
            return col;
        }
 
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return row == point.row &&
                    col == point.col;
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
 
        @Override
        public String toString() {
            return "Point{" +
                    "row=" + row +
                    ", col=" + col +
                    '}';
        }
    }
}
1
10 / 11 / 2
Регистрация: 10.07.2018
Сообщений: 70
Записей в блоге: 1
21.08.2018, 18:35
Насколько знаю, волновой алгоритм работает за O(n2). Почти всегда волновой алгоритм можно заменить обходом графа в глубину/ширину. Тогда и сложность будет O(n+m), где n - кол-во вершин, а m - кол-во рёбер в графе. Помню, решал похожую задачу. Некоторые через волновой алгоритм решили, а я поиском в глубину . Как по мне, обход графа и реализовать проще, чем волновой, и работает он быстрее.
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
21.08.2018, 18:45
Цитата Сообщение от ManyGames Посмотреть сообщение
можно заменить обходом графа в глубину
Почти никогда.
Цитата Сообщение от ManyGames Посмотреть сообщение
Некоторые через волновой алгоритм решили, а я поиском в глубину
Может таки в ширину? Что за задача была?
0
10 / 11 / 2
Регистрация: 10.07.2018
Сообщений: 70
Записей в блоге: 1
21.08.2018, 18:56
Цитата Сообщение от JIeIIIa Посмотреть сообщение
Почти никогда.
Например?)
Цитата Сообщение от JIeIIIa Посмотреть сообщение
Может таки в ширину? Что за задача была?
Нет, в глубину. Условие задачи, конечно, намного короче :
Кликните здесь для просмотра всего текста

В неориентированном невзвешенном графе требуется найти длину кратчайшего пути между двумя вершинами.

Некоторые советуют решать волновым алгоритмом, но тут можно пройтись dfs из начальной вершины, запоминая расстояния к другим в некотором массиве d. Потом просто вывести расстояние от начальной вершины к нужной. И да, BFS-ом решение тоже проходило. Кто-то вообще дейстрой и флойдом решал эту задачу..)
0
1 / 1 / 0
Регистрация: 14.01.2018
Сообщений: 102
21.08.2018, 19:07  [ТС]
Цитата Сообщение от ManyGames Посмотреть сообщение
Насколько знаю, волновой алгоритм работает за O(n2). Почти всегда волновой алгоритм можно заменить обходом графа в глубину/ширину. Тогда и сложность будет O(n+m), где n - кол-во вершин, а m - кол-во рёбер в графе. Помню, решал похожую задачу. Некоторые через волновой алгоритм решили, а я поиском в глубину . Как по мне, обход графа и реализовать проще, чем волновой, и работает он быстрее.
Обход в ширину не проходит, в комментариях к задаче писали, что сложность О(n*m*k), уже какой день голову ломаю
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
21.08.2018, 19:08
Цитата Сообщение от ManyGames Посмотреть сообщение
Условие задачи, конечно, намного короче
Как хранился граф? Какой был метод обхода в глубину?
Поиском в ширину можно быстро найти кратчайший путь. Как будет "плутать" поиск в глубину - не известно. По времени так точно дольше.
0
10 / 11 / 2
Регистрация: 10.07.2018
Сообщений: 70
Записей в блоге: 1
21.08.2018, 19:34
Цитата Сообщение от JIeIIIa Посмотреть сообщение
Как будет "плутать" поиск в глубину - не известно. По времени так точно дольше.
Видимо вы не знакомы с алгоритмом поиска в глубину.
Поиск в глубину - http://e-maxx.ru/algo/dfs
Поиск в ширину - http://e-maxx.ru/algo/bfs
Как видите, временная сложность у них одинаковая - O(n+m). Они обходят граф немного по-разному, но всё же они обходят его полностью, тем самым затратив на это одинаковое время. В то же время реализация обхода в глубину выглядит более красиво, чем обход в глубину, имхо. Но опять же, они не идентичны. Но точно могут во многих ситуациях заменить волновой алгоритм.
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
21.08.2018, 19:42
ManyGames, я ж Вас не спрашивал описание. Расскажите как решали и я дам Вам начальные данные - посмотрите на работу и сравните с поиском в ширину.

Добавлено через 2 минуты
ManyGames, ну и почитайте описание алгоритмов по Вашим же ссылкам: один находит любой путь, второй находит кратчайший путь.
0
10 / 11 / 2
Регистрация: 10.07.2018
Сообщений: 70
Записей в блоге: 1
21.08.2018, 20:10
Цитата Сообщение от JIeIIIa Посмотреть сообщение
один находит любой путь, второй находит кратчайший путь
Вероятно, тут вы правы. И посмотрел код, который я писал, всё же поиск в ширину , но всё же не волновой. Но тема то про волновой алгоритм. Мне всё же интересно, какие есть задачи, которые невозможно решить поиском в глубину/ширину, но можно решить волновым алгоритмом?
1
502 / 348 / 134
Регистрация: 14.06.2016
Сообщений: 669
21.08.2018, 20:12
Лучший ответ Сообщение было отмечено stupid_man как решение

Решение

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    void run(Scanner in, PrintWriter out){
        class Virus {
            final int x, y;
            Virus(int x, int y) { this.x = x; this.y = y; }
            int to(int tox, int toy) { return Math.abs(tox - x) + Math.abs(toy - y); }
        }
        final int width = in.nextInt(), height = in.nextInt();
        final Virus[] viruses;
        Arrays.setAll(viruses = new Virus[in.nextInt()], n -> new Virus(in.nextInt(), in.nextInt()));
 
        int result = Integer.MIN_VALUE;
 
        for (int x = 1; x <= width; x++)
            for (int y = 1; y <= height; y++) {
                int min = Integer.MAX_VALUE;
                for (Virus v : viruses) min = Math.min(min, v.to(x, y));
                result = Math.max(result, min);
            }
        out.println(result);
        out.flush();
    }
1
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
21.08.2018, 20:17
Цитата Сообщение от ManyGames Посмотреть сообщение
невозможно решить поиском в глубину/ширину, но можно решить волновым алгоритмом?
А если вспомнить, что волновой алгоритм основан на поиске в ширину, то вопрос теряет смысл
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
21.08.2018, 20:17
Помогаю со студенческими работами здесь

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Волновой алгоритм
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала и конца вводятся пользователем,...

Волновой алгоритм
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы весов неориентированного графа. Объясните...

Волновой алгоритм Ли
Помогите написать программу в Delphi (волновой алгоритм ЛИ) любую задачу. очень нужно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru