Рубрики

Минимальные затраты на покрытие заданных позиций в сетке N * M

Учитывая n * m сетку и положение некоторых полюсов, которые будут окрашены в сетке, задача состоит в том, чтобы найти минимальную стоимость для окрашивания всех полюсов. Перемещение из одной строки в другую не требует затрат, в то время как перемещение в соседний столбец связано с затратами в 1 рупию.

Примеры:

Input: n = 2, m = 2, noOfPos = 2
pos[0] = 0, 0
pos[1] = 0, 1

Output: 1
The grid is of 2*2 size and there are two poles at {0, 0} and {0, 1}. 
So we will start at {0, 0} and paint the pole and then go to
the next column to paint the pole at {0, 1} position which will
cost 1 rupee to move one column. 

Input: n = 2, m = 2, noOfPos = 2
pos[0] = {0, 0}
pos[1] = {1, 0}
Output: 0
Both poles are in the same column. So, no need to move to another column.

Подход: поскольку стоимость перемещения в столбцах является единственной, поэтому, если мы перейдем к любому столбцу, мы нарисуем все полюса в этом столбце и затем двинемся вперед. Таким образом, в основном ответом будет разница между двумя самыми дальними столбцами.

Ниже приведена обязательная реализация:

C ++

// C ++ реализация вышеуказанного подхода

  
#include <iostream>
#include <list>

  

using namespace std;

  

    // Функция поиска стоимости покраски всех полюсов

    void find(int n,int m,int p,int q[2][2])

    {

        // Чтобы сохранить все столбцы, создать список

        list <int> z ;

        int i ;

          

        for(i = 0;i < p;i++)

            z.push_back(q[i][1]);

          

        // сортировка в порядке возрастания

        z.sort();

          

        // z.back () дает максимальное значение

        // z.front () дает минимальное значение

        cout << z.back() - z.front() <<endl ;

    }

      

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

    int main()

    {

        int n = 2;

        int m = 2;

        int p = 2;

          

        int q[2][2] = {{0,0},{0,1}} ;

          

        find(n, m, p, q);

         

       return 0;

         

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

    }

Джава

// Java реализация вышеуказанного подхода

  

import java.util.*;

class solution

{

  

    // Функция поиска стоимости покраски всех полюсов

    static void find(int n,int m,int p,int q[][]) 

    

        // Чтобы сохранить все столбцы, создать список

        Vector <Integer> z= new Vector<Integer>() ; 

        int i ; 

          

        for(i = 0;i < p;i++) 

            z.add(q[i][1]); 

          

        // сортировка в порядке возрастания

        Collections.sort(z); 

          

        // z.back () дает максимальное значение

        // z.front () дает минимальное значение

        System.out.print(z.get(z.size()-1) - z.get(0) ) ; 

    

      

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

    public static void main(String args[])

    

        int n = 2

        int m = 2

        int p = 2

          

        int q[][] = {{0,0},{0,1}} ; 

          

        find(n, m, p, q); 

          

           

    

  

  

  
}
// предоставлено Арнабом Кунду

python3

# Функция найти стоимость раскраски всех полюсов

import math as ma

  

def find(n, m, p, q):

  

    # Для хранения всех столбцов

    z =[]

    for i in range(p):

        z.append(q[i][1])

  

    print(max(z)-min(z))

      

n, m, p = 2, 2, 2

q =[(0, 0), (0, 1)]

find(n, m, p, q)

C #

// C # реализация вышеуказанного подхода

using System;

using System.Collections.Generic;

  

class GFG

{

  

    // Функция поиска стоимости покраски всех полюсов

    static void find(int n, int m, int p, int [,]q) 

    

        // Чтобы сохранить все столбцы, создать список

        List <int> z = new List<int>(); 

        int i; 

          

        for(i = 0; i < p; i++) 

            z.Add(q[i, 1]); 

          

        // сортировка в порядке возрастания

        z.Sort(); 

          

        // z.back () дает максимальное значение

        // z.front () дает минимальное значение

        Console.Write(z[z.Count-1] - z[0]); 

    

      

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

    public static void Main(String []args)

    

        int n = 2; 

        int m = 2; 

        int p = 2; 

          

        int [,]q = {{0, 0}, {0, 1}}; 

          

        find(n, m, p, q); 

    

}

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

PHP

<?php 
// PHP реализация вышеуказанного подхода

  
// Функция для поиска стоимости
// раскрасить все полюса

function find($n, $m, $p, $q)

{

    // Чтобы сохранить все столбцы,

    // создаем массив

    $z = array();

      

    for($i = 0; $i < $p; $i++)

        array_push($z, $q[$i][1]);

      

    // сортировка в порядке возрастания

    sort($z);

  

    echo max($z) - min($z);

}

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

$n = 2;

$m = 2;

$p = 2;

  

$q = array(array(0, 0),

            array(0, 1));

  

find($n, $m, $p, $q);

  
// Этот код предоставлен ita_c
?> 

Выход:

1

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

Минимальные затраты на покрытие заданных позиций в сетке N * M

0.00 (0%) 0 votes