Рубрики

Минимальное время, необходимое для гниения всех апельсинов

Дана матрица размерности m * n, где каждая ячейка в матрице может иметь значения 0, 1 или 2, что имеет следующий смысл:

0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges 

Поэтому мы должны определить, какое минимальное время требуется, чтобы все апельсины стали гнилыми. Гнилой апельсин с индексами [i, j] может гнить другой свежий апельсин с индексами [i-1, j], [i + 1, j], [i, j-1], [i, j + 1] (вверх вниз, влево и вправо). Если невозможно гнить каждый апельсин, просто верните -1.

Примеры:

Input:  arr[][C] = { {2, 1, 0, 2, 1},
                     {1, 0, 1, 2, 1},
                     {1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2 time frames.


Input:  arr[][C] = { {2, 1, 0, 2, 1},
                     {0, 0, 1, 2, 1},
                     {1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.

Идея состоит в том, чтобы пользователь Breadth First Search. Ниже приведен алгоритм.

1) Create an empty Q.
2) Find all rotten oranges and enqueue them to Q. Also enqueue a delimiter to indicate the beginning of next time frame.
3) While Q is not empty do following
….3.a) Do following while delimiter in Q is not reached
…….. (i) Dequeue an orange from the queue, rot all adjacent oranges. While rotting the adjacent, make sure that the time frame is incremented only once. And the time frame is not incremented if there are no adjacent oranges.
….3.b) Dequeue the old delimiter and enqueue a new delimiter. The oranges rotten in the previous time frame lie between the two delimiters.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода.

C ++

// C ++ программа для поиска минимального времени, необходимого для выполнения всех
// апельсины гнилые
#include<bits/stdc++.h>
#define R 3
#define C 5

using namespace std;

  
// функция для проверки правильности / недействительности ячейки

bool isvalid(int i, int j)

{

    return (i >= 0 && j >= 0 && i < R && j < C);

}

  
// структура для хранения координат ячейки

struct ele {

    int x, y;

};

  
// Функция для проверки, является ли ячейка разделителем
// который есть (-1, -1)

bool isdelim(ele temp)

{

    return (temp.x == -1 && temp.y == -1);

}

  
// Функция, чтобы проверить, есть ли еще свежий
// оставшийся апельсин

bool checkall(int arr[][C])

{

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

       for (int j=0; j<C; j++)

          if (arr[i][j] == 1)

             return true;

    return false;

}

  
// Эта функция находит, можно ли гнить все апельсины или нет.
// Если возможно, то возвращает минимальное время, необходимое для гниения всего,
// в противном случае возвращает -1

int rotOranges(int arr[][C])

{

    // Создать очередь ячеек

    queue<ele> Q;

    ele temp;

    int ans = 0;

  

    // Сохраняем все ячейки с гнилым оранжевым в первом таймфрейме

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

    {

       for (int j=0; j<C; j++)

       {

            if (arr[i][j] == 2)

            {

                temp.x = i;

                temp.y = j;

                Q.push(temp);

            }

        }

    }

  

    // Отделить эти гнилые апельсины от апельсинов, которые будут гнилыми

    // из-за апельсинов в первом таймфрейме, используя разделитель (-1, -1)

    temp.x = -1;

    temp.y = -1;

    Q.push(temp);

  

    // Обрабатываем сетку, пока в очереди есть гнилые апельсины

    while (!Q.empty())

    {

        // Этот флаг используется, чтобы определить, является ли хотя бы один свежий

        // апельсин гниет из-за гнилых апельсинов в текущее время

        // кадр, чтобы мы могли увеличить количество требуемого времени.

        bool flag = false;

  

        // Обработка всех гнилых апельсинов в текущем периоде времени.

        while (!isdelim(Q.front()))

        {

            temp = Q.front();

  

            // Проверяем правую соседнюю ячейку, что если она может быть гнилой

            if (isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)

            {

                // если это первый апельсин, который прогнил, увеличить

                // посчитаем и установим флаг.

                if (!flag) ans++, flag = true;

  

                // Сделать апельсин тухлым

                arr[temp.x+1][temp.y] = 2;

  

                // толкаем соседний оранжевый в очередь

                temp.x++;

                Q.push(temp);

  

                temp.x--; // Вернемся к текущей ячейке

            }

  

            // Проверяем левую соседнюю ячейку, что если она может быть гнилой

            if (isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {

                if (!flag) ans++, flag = true;

                arr[temp.x-1][temp.y] = 2;

                temp.x--;

                Q.push(temp); // помещаем эту ячейку в очередь

                temp.x++;

            }

  

            // Проверяем верхнюю соседнюю ячейку, что если она может быть гнилой

            if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {

                if (!flag) ans++, flag = true;

                arr[temp.x][temp.y+1] = 2;

                temp.y++;

                Q.push(temp); // Переместить эту ячейку в очередь

                temp.y--;

            }

  

            // Проверяем нижнюю соседнюю ячейку на предмет гниения

            if (isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {

                if (!flag) ans++, flag = true;

                arr[temp.x][temp.y-1] = 2;

                temp.y--;

                Q.push(temp); // помещаем эту ячейку в очередь

            }

  

            Q.pop();

        }

  

        // Выделяем разделитель

        Q.pop();

  

        // Если апельсины были гнилые в текущем кадре, чем отделить

        // гнилые апельсины, использующие разделитель для следующего кадра для обработки.

        if (!Q.empty()) {

            temp.x = -1;

            temp.y = -1;

            Q.push(temp);

        }

  

        // Если очередь пуста, то для обработки не осталось гнилых апельсинов, поэтому выходим

    }

  

    // Возвращаем -1, если все аранжировки не могут гнить, иначе -1.

    return (checkall(arr))? -1: ans;

}

  
// Программа движения

int main()

{

    int arr[][C] = { {2, 1, 0, 2, 1},

                     {1, 0, 1, 2, 1},

                     {1, 0, 0, 2, 1}};

    int ans = rotOranges(arr);

    if (ans == -1)

        cout << "All oranges cannot rotn";

    else

         cout << "Time required for all oranges to rot => " << ans << endl;

    return 0;

}

Джава

// Java-программа, чтобы найти минимальное время, необходимое, чтобы сделать все
// апельсины гнилые

  

import java.util.LinkedList;

import java.util.Queue;

  

public class RotOrange 

{

    public final static int R = 3;

    public final static int C = 5;

      

    // структура для хранения координат ячейки

    static class Ele

    {

        int x = 0;

        int y = 0;

        Ele(int x,int y)

        {

            this.x = x;

            this.y = y;

        }

    }

      

    // функция для проверки правильности / недействительности ячейки

    static boolean isValid(int i, int j)

    {

        return (i >= 0 && j >= 0 && i < R && j < C);

    }

      

  

    // Функция для проверки, является ли ячейка разделителем

    // который есть (-1, -1)

    static boolean isDelim(Ele temp)

    {

        return (temp.x == -1 && temp.y == -1);

    }

      

    // Функция, чтобы проверить, есть ли еще свежий

    // оставшийся апельсин

    static boolean checkAll(int arr[][])

    {

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

               for (int j=0; j<C; j++)

                  if (arr[i][j] == 1)

                     return true;

         return false;

    }

      

    // Эта функция находит, можно ли гнить все апельсины или нет.

    // Если возможно, то возвращает минимальное время, необходимое для гниения всего,

    // в противном случае возвращает -1

    static int rotOranges(int arr[][])

    {

        // Создать очередь ячеек

        Queue<Ele> Q=new LinkedList<>();

        Ele temp; 

        int ans = 0;

         // Сохраняем все ячейки с гнилым оранжевым в первом таймфрейме

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

           for (int j=0; j < C; j++)

               if (arr[i][j] == 2)

                   Q.add(new Ele(i,j));

                  

        // Отделить эти гнилые апельсины от апельсинов, которые будут гнилыми

        // из-за апельсинов в первом таймфрейме, используя разделитель (-1, -1)

        Q.add(new Ele(-1,-1));

          

        // Обрабатываем сетку, пока в очереди есть гнилые апельсины

        while(!Q.isEmpty())

        {

            // Этот флаг используется, чтобы определить, является ли хотя бы один свежий

            // апельсин гниет из-за гнилых апельсинов в текущее время

            // кадр, чтобы мы могли увеличить количество требуемого времени.

            boolean flag = false;

              

            // Обработка всех гнилых апельсинов в текущем периоде времени.

            while(!isDelim(Q.peek()))

            {

                temp = Q.peek();

                  

                // Проверяем правую соседнюю ячейку, что если она может быть гнилой

                if(isValid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)

                {

                    if(!flag)

                    {

                        // если это первый апельсин, который прогнил, увеличить

                        // посчитаем и установим флаг.

                        ans++;

                        flag = true;

                    }

                    // Сделать апельсин тухлым

                    arr[temp.x+1][temp.y] = 2;

                      

                    // толкаем соседний оранжевый в очередь

                    temp.x++;

                    Q.add(new Ele(temp.x,temp.y));

                      

                    // Вернемся к текущей ячейке

                    temp.x--;

                }

                  

                // Проверяем левую соседнюю ячейку, что если она может быть гнилой

                if (isValid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1)

                 {

                        if (!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x-1][temp.y] = 2;

                        temp.x--;

                        Q.add(new Ele(temp.x,temp.y)); // помещаем эту ячейку в очередь

                        temp.x++;

                 }

                  

                // Проверяем верхнюю соседнюю ячейку, что если она может быть гнилой

                 if (isValid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {

                        if(!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x][temp.y+1] = 2;

                        temp.y++;

                        Q.add(new Ele(temp.x,temp.y)); // Переместить эту ячейку в очередь

                        temp.y--;

                    }

                   

                 // Проверяем нижнюю соседнюю ячейку на предмет гниения

                 if (isValid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1

                 {

                        if (!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x][temp.y-1] = 2;

                        temp.y--;

                        Q.add(new Ele(temp.x,temp.y)); // помещаем эту ячейку в очередь

                 }

                 Q.remove();

                   

            }

            // Выделяем разделитель

            Q.remove();

              

            // Если апельсины были гнилые в текущем кадре, чем отделить

            // гнилые апельсины, использующие разделитель для следующего кадра для обработки.

            if (!Q.isEmpty()) 

            {

                Q.add(new Ele(-1,-1));

            }

              

            // Если очередь пуста, то для обработки не осталось гнилых апельсинов, поэтому выходим

        }

          

        // Возвращаем -1, если все аранжировки не могут гнить, иначе -1.s

        return (checkAll(arr))? -1: ans;

          

    }

      

    // Программа движения

    public static void main(String[] args) 

    {

        int arr[][] = { {2, 1, 0, 2, 1},

                        {1, 0, 1, 2, 1},

                        {1, 0, 0, 2, 1}};

        int ans = rotOranges(arr);

        if(ans == -1)

            System.out.println("All oranges cannot rot");

        else

            System.out.println("Time required for all oranges to rot = " + ans);

    }

  
}
// Этот код предоставлен Sumit Ghosh

C #

// C # программа для поиска минимального времени
// требуется сделать все апельсины гнилыми

using System;

using System.Collections.Generic;

  

class GFG

{

    public const int R = 3;

    public const int C = 5;

  

    // структура для хранения

    // координаты ячейки

    public class Ele

    {

        public int x = 0;

        public int y = 0;

        public Ele(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

    }

  

    // функция для проверки наличия ячейки

    // действителен / недействителен

    public static bool isValid(int i, int j)

    {

        return (i >= 0 && j >= 0 && 

                i < R && j < C);

    }

  

  

    // Функция для проверки наличия ячейки

    // это разделитель, который равен (-1, -1)

    public static bool isDelim(Ele temp)

    {

        return (temp.x == -1 && temp.y == -1);

    }

  

    // Функция, чтобы проверить, есть ли

    // остаётся свежий апельсин

    public static bool checkAll(int[][] arr)

    {

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

        {

            for (int j = 0; j < C; j++)

            {

                if (arr[i][j] == 1)

                {

                    return true;

                }

            }

        }

        return false;

    }

  

    // Эта функция находит, если это возможно

    // гнить все апельсины или нет. Если возможно,

    // тогда возвращается минимальное время

    // сгнить все, иначе возвращает -1

    public static int rotOranges(int[][] arr)

    {

        // Создать очередь ячеек

        LinkedList<Ele> Q = new LinkedList<Ele>();

        Ele temp;

        int ans = 0;

          

        // Сохраняем все клетки с гнилой

        // оранжевый в первом таймфрейме

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

        {

        for (int j = 0; j < C; j++)

        {

            if (arr[i][j] == 2)

            {

                Q.AddLast(new Ele(i, j));

            }

        }

        }

  

        // Отделим эти гнилые апельсины от

        // апельсины, которые будут гнить

        // из-за апельсинов в первом таймфрейме

        // используя разделитель (-1, -1)

        Q.AddLast(new Ele(-1,-1));

  

        // Обрабатываем сетку, пока есть

        // гнилые апельсины в очереди

        while (Q.Count > 0)

        {

            // Этот флаг используется для определения

            // будь хоть один свежий

            // апельсин гниет из-за гниения

            // апельсины в текущем таймфрейме

            // мы можем увеличить количество

            // требуемое время.

            bool flag = false;

  

            // Обрабатываем все гнилые апельсины

            // в текущем временном интервале.

            while (!isDelim(Q.First.Value))

            {

                temp = Q.First.Value;

  

                // Проверяем правую соседнюю ячейку

                // если это может быть гнилым

                if (isValid(temp.x + 1, temp.y) && 

                        arr[temp.x + 1][temp.y] == 1)

                {

                    if (!flag)

                    {

                        // если это первый апельсин

                        // прогни, увеличивай

                        // посчитаем и установим флаг.

                        ans++;

                        flag = true;

                    }

                      

                    // Сделать апельсин тухлым

                    arr[temp.x + 1][temp.y] = 2;

  

                    // толкаем соседний оранжевый в очередь

                    temp.x++;

                    Q.AddLast(new Ele(temp.x,temp.y));

  

                    // Вернемся к текущей ячейке

                    temp.x--;

                }

  

                // Проверяем левую соседнюю ячейку

                // если это может быть гнилым

                if (isValid(temp.x - 1, temp.y) && 

                        arr[temp.x - 1][temp.y] == 1)

                {

                        if (!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x - 1][temp.y] = 2;

                        temp.x--;

                          

                        // помещаем эту ячейку в очередь

                        Q.AddLast(new Ele(temp.x,temp.y)); 

                        temp.x++;

                }

  

                // Проверяем верхнюю соседнюю ячейку, которая

                // если это может быть гнилым

                if (isValid(temp.x, temp.y + 1) && 

                        arr[temp.x][temp.y + 1] == 1)

                {

                        if (!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x][temp.y + 1] = 2;

                        temp.y++;

                          

                        // Переместить эту ячейку в очередь

                        Q.AddLast(new Ele(temp.x,temp.y)); 

                        temp.y--;

                }

  

                // Проверяем нижнюю соседнюю ячейку

                // если это может быть гнилым

                if (isValid(temp.x, temp.y - 1) && 

                        arr[temp.x][temp.y - 1] == 1)

                {

                        if (!flag)

                        {

                            ans++;

                            flag = true;

                        }

                        arr[temp.x][temp.y - 1] = 2;

                        temp.y--;

                          

                        // помещаем эту ячейку в очередь

                        Q.AddLast(new Ele(temp.x,temp.y)); 

                }

                Q.RemoveFirst();

  

            }

              

            // Выделяем разделитель

            Q.RemoveFirst();

  

            // Если бы апельсины были гнилыми в течении

            // кадр, чем отделить гнилое

            // апельсины, использующие разделитель для

            // следующий кадр для обработки.

            if (Q.Count > 0)

            {

                Q.AddLast(new Ele(-1,-1));

            }

  

            // Если очередь пуста, то не гнилая

            // осталось обработать апельсины, чтобы выйти

        }

  

        // Возвращаем -1, если все аранжировки могут

        // не гниет, иначе -1.s

        return (checkAll(arr)) ? -1: ans;

  

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        int[][] arr = new int[][]

        {

            new int[] {2, 1, 0, 2, 1},

            new int[] {1, 0, 1, 2, 1},

            new int[] {1, 0, 0, 2, 1}

        };

          

        int ans = rotOranges(arr);

        if (ans == -1)

        {

            Console.WriteLine("All oranges cannot rot");

        }

        else

        {

            Console.WriteLine("Time required for all " +

                              "oranges to rot => " + ans);

        }

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

Time required for all oranges to rot => 2

Спасибо Gaurav Ahirwar за предложенное выше решение.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Минимальное время, необходимое для гниения всех апельсинов

0.00 (0%) 0 votes