e-olymp 9414. Убить всех термитов

03/10/2020 by Андрей Метасов

Условие задачи

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

Входные данные

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

Выходные данные

Выведите минимальное количество отравленных вершин.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	2 1	1
3	8 1 1 2 1 2 3 2	2
4	5 1 2 1 4	1
5	16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15	3
6	10 1 2 3 3 1 2 3 7 9	2
7	8 1 1 3 3 1 6 6	2

Код

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static final int NMAX = 100001;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);
    static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);
    static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);
    static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);
    static int ans = 0;

    public static void kills(int v, int p)
    {
        if (v == p) kills(tree.get(v).get(0), v);
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);
        if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);
        return;
    }

    public static void goup(int v, int p)
    {
        if (v == p)
        {
            for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);
            killed.set(v, 0);
            return;
        }
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);
        if (tree.get(v).size() >= 3)
        {
            killed.set(v, killed.get(v) + 1);
            return;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i=0;i<NMAX; i++)
        {
            tree.add(new ArrayList<Integer>());
            dist.add(0);
            used.add(false);
            killed.add(0);
        }
        int n,v;
        n = in.nextInt();
        if (n <= 5) {System.out.print(1); return;} // Частный случай
        tree.get(1).add(0); // Корень тоже должен быть "развилкой"
        ArrayList<Integer> leaves = new ArrayList<Integer> ();
        for (int i = 1; i < n; i++)
        {
            v = in.nextInt();
            tree.get(v).add(i+1);
            tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают
        }

        for (int i = 1; i <= n; i++)
        {
            if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья
        }

        LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);
        q.offer(1); used.set(1, true);
        while (!q.isEmpty())
        {
            int qv = q.poll();
            used.set(qv, true);
            for (Integer to : tree.get(qv))                //BFS заполняющий вектор dist
            {
                if (!used.get(to))
                {
                    q.offer(to);
                    dist.set(to, dist.get(qv)+1);
                }
            }
        }

        for (Integer l : leaves)
        {
            kills(l, l);        // Первый этап - запросы от каждого листа
        }

        int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева
        int wentup = 1;
        while (wentup != 0)
        {
            wentup = 0;
            for (int l = maxdist; l > 0; l--)
            {
                for (int i = 2; i <= n; i++)
                {
                    if (killed.get(i) == 1 && dist.get(i) == l)
                    {
                        goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
                        wentup++;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок
        System.out.print(ans);
    }
}

100

101

102

103

104

105

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Main {

static final int NMAX = 100001;

static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);

static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);

static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);

static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);

static int ans = 0;

public static void kills(int v, int p)

{

if (v == p) kills(tree.get(v).get(0), v);

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);

if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);

return;

}

public static void goup(int v, int p)

{

if (v == p)

{

for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);

killed.set(v, 0);

return;

}

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);

if (tree.get(v).size() >= 3)

{

killed.set(v, killed.get(v) + 1);

return;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

for (int i=0;i<NMAX; i++)

{

tree.add(new ArrayList<Integer>());

dist.add(0);

used.add(false);

killed.add(0);

}

int n,v;

n = in.nextInt();

if (n <= 5) {System.out.print(1); return;} // Частный случай

tree.get(1).add(0); // Корень тоже должен быть "развилкой"

ArrayList<Integer> leaves = new ArrayList<Integer> ();

for (int i = 1; i < n; i++)

{

v = in.nextInt();

tree.get(v).add(i+1);

tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают

}

for (int i = 1; i <= n; i++)

{

if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья

}

LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);

q.offer(1); used.set(1, true);

while (!q.isEmpty())

{

int qv = q.poll();

used.set(qv, true);

for (Integer to : tree.get(qv)) //BFS заполняющий вектор dist

{

if (!used.get(to))

{

q.offer(to);

dist.set(to, dist.get(qv)+1);

}

for (Integer l : leaves)

{

kills(l, l); // Первый этап - запросы от каждого листа

}

int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева

int wentup = 1;

while (wentup != 0)

{

wentup = 0;

for (int l = maxdist; l > 0; l--)

{

for (int i = 2; i <= n; i++)

{

if (killed.get(i) == 1 && dist.get(i) == l)

{

goup(i, i); //Этап 2 - поднятие "недошедших" запросов

wentup++;

}

for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок

System.out.print(ans);

}

Решение задачи

Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

Увы, первый этап не идеален и может «не донести» запросы в нужное место, т.к. некоторые развилки (а именно — соединяющие лист и другую развилку) могут остаться с одним запросом и не быть закрытыми. Если таких много, термит все еще может ходить между листами. Например, в таком дереве:

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в ArrayList<ArrayList<Integer>> tree . Количество запросов для вершины $i$ хранится в killed.get(i). Стандартный ArrayList used для поиска в ширину и dist- ArrayList расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree.get(v).get(0).
tree.get(v).size() == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
tree.get(v).size() >= 3 — попали в развилку. Увеличиваем ее значение killed.get(v) и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в tree (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в ArrayList leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит ArrayList dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed.get(i) == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed.get(i) >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

e-olymp 88. Месть Ли Чака

15/10/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

Входные данные

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

Код программы

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{

    private static class Node {
        private int i;
        private int j;

        private Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    private static void fill(int[][] a, int value) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value;
            }
        }
    }

    private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        moves[start.i][start.j] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
    }

    private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        moves[start.i][start.j] = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (map[i][j] == 'e') {
                return true;
            }
            if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(bufferedReader.readLine());
        for (int r = 0; r < tests; r++) {
            String[] sizes = bufferedReader.readLine().split(" ");
            int n = Integer.parseInt(sizes[0]);
            int m = Integer.parseInt(sizes[1]);
            char[][] map = new char[n][m];
            Node g = null;
            Node l = null;
            Node e = null;
            for (int i = 0; i < n; i++) {
                map[i] = bufferedReader.readLine().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 'g') {
                        g = new Node(i, j);
                    }
                    else if (map[i][j] == 'l') {
                        l = new Node(i, j);
                    }
                    else if (map[i][j] == 'e') {
                        e = new Node(i, j);
                    }
                }
            }
            int[][] secondPlayerDistances = new int[n][m];
            fill(secondPlayerDistances, Integer.MAX_VALUE);
            bfsSecondPlayer(map, secondPlayerDistances, l);
            int[][] firstPlayerDistances = new int[n][m];
            fill(firstPlayerDistances, Integer.MAX_VALUE);
            boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
            System.out.println(ok ? "YES" : "NO");
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class Main{

private static class Node {

private int i;

private int j;

private Node(int i, int j) {

this.i = i;

this.j = j;

}

private static void fill(int[][] a, int value) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j < a[i].length; j++) {

a[i][j] = value;

}

private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {

Queue<Node> queue = new LinkedList<>();

moves[start.i][start.j] = 0;

queue.add(start);

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {

Queue<Node> queue = new LinkedList<>();

queue.add(start);

moves[start.i][start.j] = 0;

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (map[i][j] == 'e') {

return true;

}

if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

return false;

}

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int tests = Integer.parseInt(bufferedReader.readLine());

for (int r = 0; r < tests; r++) {

String[] sizes = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(sizes[0]);

int m = Integer.parseInt(sizes[1]);

char[][] map = new char[n][m];

Node g = null;

Node l = null;

Node e = null;

for (int i = 0; i < n; i++) {

map[i] = bufferedReader.readLine().toCharArray();

for (int j = 0; j < m; j++) {

if (map[i][j] == 'g') {

g = new Node(i, j);

}

else if (map[i][j] == 'l') {

l = new Node(i, j);

}

else if (map[i][j] == 'e') {

e = new Node(i, j);

}

int[][] secondPlayerDistances = new int[n][m];

fill(secondPlayerDistances, Integer.MAX_VALUE);

bfsSecondPlayer(map, secondPlayerDistances, l);

int[][] firstPlayerDistances = new int[n][m];

fill(firstPlayerDistances, Integer.MAX_VALUE);

boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);

System.out.println(ok ? "YES" : "NO");

}

Решение задачи

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 982. Связность

26/08/2016 by Дарья Пиндус

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

Входные данные

В первой строке заданы количество вершин $n$ и ребер $m$ в графе соответственно $(1 \leq n \leq 100, 1 \leq m \leq 10000)$ . Каждая из следующих m строк содержит по два числа $u_i$ и $v_i$ $(1 \leq u_i, v_i \leq n);$ каждая такая строка означает, что в графе существует ребро между вершинами $u_i$ и $v_i$ .

Выходные данные

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	5 4 1 2 5 3 4 5 3 4	NO
3	5 4 1 2 5 1 3 5 4 3	YES

Код программы

import java.util.*;
 
class Graph {
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        ArrayList<Integer> gr[] = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            gr[i] = new ArrayList<>();
        }
 
        int s = 0;
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            gr[u - 1].add(v - 1);
            gr[v - 1].add(u - 1);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        queue.push(s);
        boolean used[] = new boolean[n];
        used[s] = true;
 
        while (!queue.isEmpty()) {
            int v = queue.peek();
            queue.pop();
            for (int i = 0; i < gr[v].size(); ++i) {
                int to = gr[v].get(i);
                if (!used[to]) {
                    used[to] = true;
                    queue.push(to);
                }
            }
        }
        String answer = "YES";
        for (int i = 0; i < used.length; i++) {
            if (used[i] == false) {
                answer = "NO";
            }
        }
        System.out.println(answer);
    }
}

import java.util.*;

class Graph {

public static void main(String[] args) {

int n, m;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

m = scanner.nextInt();

ArrayList<Integer> gr[] = new ArrayList[n];

for (int i = 0; i < n; i++) {

gr[i] = new ArrayList<>();

}

int s = 0;

for (int i = 0; i < m; i++) {

int u, v;

u = scanner.nextInt();

v = scanner.nextInt();

gr[u - 1].add(v - 1);

gr[v - 1].add(u - 1);

}

LinkedList<Integer> queue = new LinkedList<>();

queue.push(s);

boolean used[] = new boolean[n];

used[s] = true;

while (!queue.isEmpty()) {

int v = queue.peek();

queue.pop();

for (int i = 0; i < gr[v].size(); ++i) {

int to = gr[v].get(i);

if (!used[to]) {

used[to] = true;

queue.push(to);

}

String answer = "YES";

for (int i = 0; i < used.length; i++) {

if (used[i] == false) {

answer = "NO";

}

System.out.println(answer);

}

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

Ссылка на Ideone

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: поиск в ширину

e-olymp 9414. Убить всех термитов

Условие задачи

Входные данные

Выходные данные

Тесты

Код

Решение задачи

Первый этап

Второй этап

Описание алгоритма

Подготовка

Первый этап

Второй этап

e-olymp 88. Месть Ли Чака

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки

e-olymp 982. Связность