алгоритм горизонта

Question

Как мне найти вершины ломаной, которая окружает силуэт на этом изображении?

Возможные входные данные для приведенного выше примера:

WIDTH  HEIGHT  POSITION
  3       9       17
  5       9        9
 12       4        8
  3      11        3
 10       7        1
  2       3       19

Так что для этого примера решение будет

[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), 
 (9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), 
 (20, 9), (20, 3), (21, 3), (21, 0)]

Answer 1

Это довольно просто.Создайте массив, который имеет длину оси X, инициализируйте до 0. По мере чтения во входных данных запишите высоты в этот массив, если высота> = текущее значение в этом месте массива.

Затем просто зациклите массив, и каждый раз, когда значение изменяется, это вершина.

В основном:

int heights[SIZE] = {0};
int i, width, pos, height, prev = -1;
while (scanf("%d %d %d", &width, &height, &pos) == 3) {
    for (i = 0; i < width; ++i) {
        if (heights[pos+i] < height)
            heights[pos+i] = height;
    }
}

for (i = 0; i < SIZE; ++i) {
    if (heights[i] != prev) {
        printf("(%d,%d) ", i+1, heights[i]);
        prev = heights[i];
    }
}
printf("\n");

Answer 2

http://online -judge.uva.es / p / v1 / 105.html - это то место, где я изначально увидел проблему

А у Алгоритмиста есть объяснение решения: http://www.algorithmist.com/index.php/UVa_105

Answer 3

Я решил эту проблему, используя алгоритм стреловидности.Это решение класса Python.

есть две клавиши: 1) использование переменной «точки» для сохранения всех левых и правых точек и их высот, а также знак высоты для указания, являются ли точки левыми или правыми.2) переменная «active» используется для сохранения всех активных строк, которые были отсканированы.

решение класса: # @param {целое число [] []} зданий # @return {целое число [] []} def getSkyline (собственная личность, здания): если len (здания) == 0: возвращать []если len (здания) == 1: вернуть [[здания [0] [0], здания [0] [2]], [здания [0] [1], 0]]

    points=[]
    for building in buildings:
        points+=[[building[0],building[2]]]
        points+=[[building[1],-building[2]]] # the negative sign means this point is a right point
    points=sorted(points, key=lambda x: x[0])

    moving, active, res, current=0, [0], [],-1

    while moving<len(points):
        i=moving
        while i<=len(points):
            if i<len(points) and points[i][0]==points[moving][0]:
                if points[i][1]>0:
                    active+=[points[i][1]]
                    if points[i][1]>current:
                        current=points[i][1]
                        if len(res)>0 and res[-1][0]==points[i][0]: 
                            res[-1][1]=current
                        else:
                            res+=[[points[moving][0], current]]
                else:
                    active.remove(-points[i][1]) #remove height of the lines than have been finished with scanning
                i+=1
            else:
                break
        if max(active)<current:
            current=max(active)
            res+=[[points[moving][0], current]] 
        moving=i
    return res 

Answer 4

В наивном случае это не кажется очень сложным алгоритмом. Вы знаете, станет ли размер ввода большим / насколько большим?

Моя первая попытка: попытаться двигаться слева направо. Сначала выберите блок с крайним левым краем, который существует на исходной линии. Поднимитесь на его вершину. Найти все блоки с левым краем между текущей точкой и верхней правой точкой текущего блока. Из этого набора выберите ближайший (но проверьте на крайние случаи, каламбур не предназначен). Если набор пуст, начните прокладывать путь вниз по правой стороне блока, ища другие блоки, которые вы можете перехватить.

По сути, именно так вы и проследите это своим глазом.

Вы можете сделать некоторую простую оптимизацию, сохраняя отсортированные списки и затем ища списки, а не находя наборы и копаясь. Например, вы можете сохранить 4 отсортированных списка блоков, каждый из которых отсортирован по координатам x или y одной из сторон.

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

Answer 5

Мое решение проблемы, как описано здесь https://leetcode.com/problems/the-skyline-problem/, оно повторяет список зданий дважды, однако это можно объединить в одну итерацию. Тем не менее, есть более оптимальные подходы, если вы рассмотрите чисто алгоритмическое решение, объясненное здесь http://www.algorithmist.com/index.php/UVa_105

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        // The final result.
        vector<pair<int, int>> result;

        // To hold information about the buildings
        std::set<BuildingInformation> buildingInformation;

        // Go through each building, and store information about the start and end heights.
        for ( vector<vector<int>>::iterator buildingIt = buildings.begin( ); buildingIt != buildings.end( ); ++buildingIt ) {
            BuildingInformation buildingStart;
            buildingStart.x = (*buildingIt)[0];
            buildingStart.h = (*buildingIt)[2];
            buildingStart.StartOrEnd = Start;
            buildingInformation.insert(buildingStart);
            buildingStart.x = (*buildingIt)[1];
            buildingStart.StartOrEnd = End;
            buildingInformation.insert(buildingStart);
        }

        // Keep track of the current height.
        int currentHeight = 0;

        // A map of active building heights against number of buildings (to handle multiple buildings overlapping with same height).
        // As it is a map, it'll be sorted by key, which is the height.
        std::map<int, int> heights;

        // Go through each building information that we generated earlier.
        for ( std::set<BuildingInformation>::iterator it = buildingInformation.begin( ); it != buildingInformation.end( ); ++it ) {
            if ( it->StartOrEnd == Start ) {
                // This is a start point, do we have this height already in our map?
                if ( heights.find( it->h ) != heights.end( ) ) {
                    // Yes, increment count of active buildings with this height/
                    heights[ it->h ] += 1;    
                } else {
                    // Nope, add this building to our map.
                    heights[ it->h ] = 1;  
                }

                // Check if building height is taller than current height.
                if ( it->h > currentHeight ) {
                    // Update current height and add marker to results.
                    currentHeight = it->h;
                    result.push_back( pair<int, int>( it->x, currentHeight ) );
                }
            } else {
                // This is an end point, get iterator into our heights map.
                std::map<int, int>::iterator heightIt = heights.find( it->h );

                // Reduce by one.
                heightIt->second -= 1;

                // If this was the last building of the current height in the map...
                if ( heightIt->second == 0 ) {
                    // Remove from heights map.
                    heights.erase( heightIt );

                    // If our height was the current height...
                    if ( it->h == currentHeight ) {
                        // If we have no more active buildings...
                        if ( heights.size( ) == 0 ) {
                            // Current height is zero.
                            currentHeight = 0;
                        } else {
                            // Otherwise, get iterator to one past last.
                            heightIt = heights.end( );

                            // Go back to get last valid iterator.
                            --heightIt;

                            // Store current height.
                            currentHeight = heightIt->first;
                        }

                        // Add marker to results.
                        result.push_back( pair<int, int>( it->x, currentHeight ) );
                    }
                }
            }
        }

        return result;
    }
private:
    // Is this a building start or end?
    enum BuildingStartOrEnd
    {
        Start = 0,
        End
    };

    // Information about building, there are two of these for each building, one for start, one for end.
    struct BuildingInformation
    {
        int x;
        int h;
        BuildingStartOrEnd StartOrEnd;

        // The ordering algorithm for the key, the rules we want to implement is keys are put in X order, and
        // in the case of a tie (x values the same), we want Start pieces to come before End pieces (this is
        // to handle cases where an old building ends and a new building begins on same X index, in which case
        // we want to process the new start before processing the old end), however if we have two Start pieces
        // at the same index, we wish to favour taller pieces (in this scenario we want to add a marker for the
        // tallest building), finally if we have two End pieces at the same index, we wish to prefer lower
        // pieces, as when multiple buildings end, we only want to add one result for the ultimate lowest point.
        bool operator < ( const BuildingInformation & rhs ) const
        {
            if ( x == rhs.x )
            {
                if ( StartOrEnd == rhs.StartOrEnd ) {
                    if ( StartOrEnd == Start )
                        return h > rhs.h;
                    else
                        return h < rhs.h;
                } else {
                    return StartOrEnd < rhs.StartOrEnd;
                }
            }

            return x < rhs.x;
        }
    };
};

Answer 6

Я создал класс Java, чтобы попытаться решить эту проблему.Класс включает в себя методы для генерации, решения и печати наборов данных.Я не тестировал подробно, возможно, осталось несколько ошибок.Кроме того, моё решение может быть излишне сложным, но оно предназначено для работы (теоретически) для недискретных значений высоты и координат.

import java.util.Random;

public class Skyline {

    private int[][] buildings;
    private int[][] skyline;

    private int maxLength;
    private int maxHeight;

    public Skyline(int buildings, int maxLength, int maxHeight) {
        this.maxLength = maxLength;
        this.maxHeight = maxHeight;
        makeRandom(buildings);
    }

    public Skyline(int[][] buildings, int dimensions) {
        this.maxLength = maxLength;
        this.maxHeight = maxHeight;
        this.buildings = buildings;
    }

    public void makeRandom(int buildings) {
        this.buildings = new int[buildings][3];

        Random rand = new Random();

        for(int i = 0; i < buildings; i++) {
            int start = rand.nextInt(maxLength-3);
            int end = rand.nextInt(maxLength - start - 1) + start + 1;
            int height = rand.nextInt(maxHeight-1) + 1;

            this.buildings[i][0] = start;
            this.buildings[i][1] = height;
            this.buildings[i][2] = end; 
        }

        boolean swapped = true;
        while(swapped) {
            swapped = false;
            for(int i = 0; i < this.buildings.length-1; i++) {
                if(this.buildings[i][0] > this.buildings[i+1][0]) {
                    swapped = true;
                    int[] temp = this.buildings[i];
                    this.buildings[i] = this.buildings[i+1];
                    this.buildings[i+1] = temp;
                }
            }
        }

//        this.buildings[0][0] = 2;
//        this.buildings[0][1] = 3;
//        this.buildings[0][2] = 8;
    }

    public void printBuildings() {
        print(this.buildings, false);
    }
    public void printSkyline() {
        print(this.buildings, true);
    }

    public void print(int[][] buildings, boolean outline) {
        char[][] str = new char[this.maxLength][this.maxHeight];
        for(int i = 0; i < this.maxLength; i++) {
            for(int j = 0; j < this.maxHeight; j++) {
                str[i][j] = '.';
            }
        }

        for(int i = 0; i < buildings.length; i++) {
            int start = buildings[i][0];
            int height = buildings[i][1];
            int end = buildings[i][2];

            //print the starting vertical
            for(int j = 0; j < height; j++) {
                if(outline) str[start][j] =  str[start][j] == '|' ? '.' : '|';
                else str[start][j] = '|';
            }

            //print the ending vertical
            for(int j = 0; j < height; j++) {
                if(outline) str[end][j] = str[end][j] == '|' ? '.' : '|';
                else str[end][j] =  '|';
            }

            //print the horizontal
            if(height > 0) {
                for(int j = start; j <= end; j++) {
                    str[j][height] = str[j][height] == '|' ? '|' : '-';
                }
            }

        }

        for(int i = maxHeight-1; i >= 0; i--) {
            for(int j = 0; j < maxLength; j++) {
                System.out.print(str[j][i]);
            }
            System.out.println();
        }

        System.out.println();
    }

    public void solveSkyline() {

        for(int i = 0; i < buildings.length; i++) {
            boolean reduced = true;
            while(reduced) {
                reduced = false;
                for(int j = i+1; j < buildings.length; j++) {
                    if(buildings[j][0] < buildings[i][2] && buildings[j][1] > buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //if intersecting building is taller, and longer
                        buildings[i][2] = buildings[j][0];  
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] <= buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //intersecting building is shorter, but longer
                        buildings[j][0] = buildings[i][2]; 
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] > 0 && buildings[j][1] < buildings[i][1] && buildings[j][2] <= buildings[i][2]) {  //building is invisible, so ignore it
                        buildings[j][1] = 0;
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][2] <= buildings[i][2] && buildings[j][1] > buildings[i][1]) {
                        int[] newBuilding = new int[]{buildings[j][2], buildings[i][1], buildings[i][2]};
                        int[][] newBuildings = new int[buildings.length+1][3];
                        boolean inserted = false;
                        buildings[i][2] = buildings[j][0];       
                        for(int k = 0; k < buildings.length; k++) {
                            if(inserted == false) {
                                if(newBuilding[0] < buildings[k][0]) {
                                    newBuildings[k] = newBuilding;
                                    newBuildings[k+1] = buildings[k];
                                    inserted = true;
                                } else {
                                    newBuildings[k] = buildings[k];
                                }
                            } 
                            if(inserted == false && k == buildings.length - 1) {
                                newBuildings[k+1] = newBuilding;
                            } else {
                                newBuildings[k+1] = buildings[k];
                            }
                        }
                        buildings = newBuildings;
                        reduced = true;
                        break;
                    }
                }
            }
        }
    }

    public static void main(String args[]) {
        Skyline s = new Skyline(5, 100, 10);

        s.printBuildings();
        s.solveSkyline();
        s.printBuildings();

        s.printSkyline();
    } 
}