10 Çeşit İnsan

Bu soruyu takip edin: 10 Çeşit Kişi Açık Kattis Problemi Zaman Sınırı C ++ 'ı Aştı

Bu soruya bağlı bulmacayı çözer.

DijkstraÖğeleri bulmak için algoritma kullanıyorum .
Tek bükülme, her arama yaptığımda, aramanın sınır listesini bir Zone. Sonraki bir aramada mevcut "Bölge", mevcut bir Bölge ile çarpışırsa, sınır listelerini birleştirir ve eski bölgeyi mevcut bölgeye getiririm.

Aranan kareler doğrudan haritada saklanır 0 veya 1 orijinal değer anlamına gelirken, herhangi bir değer> = 100 bir bölge numarası anlamına gelir (bölgeyi elde etmek için 100 çıkarın). Daha sonra bu değeri, zoneMapait olduğu bölgeyi almak için (bölgeler klonlanırsa bu eşlemeyi güncel tutar) içinde kullanabilirsiniz.

Denedim, A*ancak bu kadar küçük bir sorun alanı için, daha sonra hangi öğeyi arayacağınızı bilmek için sıralı bir liste tutmanız gerektiğinden zamanı ikiye katlıyor. Sınır listesini sıralı tutmak için sınıftaki en geri kalan A*şeyleri Zoneyorumlanmış bölümler olarak görebilirsiniz.

#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <functional>

struct Point: public std::pair<int, int>
{
    friend std::istream& operator>>(std::istream& str, Point& dst)
    {
        return str >> dst.first >> dst.second;
    }
    friend std::ostream& operator<<(std::ostream& str, Point const& src)
    {
        return str << "[" << src.first << "," << src.second << "] ";
    }
};

class Zone
{
    Point                       dst;
    char                        type;
    int                         id;
    std::vector<Point>          boundry;
    int distsq(Point const& p) const
    {
        int x = std::abs(p.first - dst.first);
        int y = std::abs(p.second - dst.second);
        return x * x + y * y;
    }
    bool order(Point const& lhs, Point const& rhs) const
    {
        return distsq(lhs) > distsq(rhs);
    }

    public:
        Zone(char type, int id, Point dst)
            : type(type)
            , id(id)
            , dst(dst)
        {}
        char getType() const {return type;}
        int  getId()   const {return id;}
        void updateDestination(Point const& d)
        {
            using namespace std::placeholders;
            dst = d;
            //std::make_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
        }
        bool empty() const          {return boundry.empty();}
        void push(Point const& p)
        {
            using namespace std::placeholders;
            boundry.emplace_back(p);
            //std::push_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
        }
        void pop()
        {
            using namespace std::placeholders;
            //std::pop_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
            boundry.pop_back();
        }
        Point top()                 {return boundry./*front*/back();}
        void addZoneBoundry(Zone const& src)
        {
            boundry.reserve(boundry.size() + src.boundry.size());
            using namespace std::placeholders;
            for (auto const& p: src.boundry) {
                boundry.emplace_back(p);
                //std::push_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
            }
        }
};

class Maze
{
    std::vector<std::vector<int>>   maze;
    std::vector<Zone>               zoneInfo;
    std::map<int, int>              zoneMap;

    public:

    Maze()
    {
        zoneInfo.reserve(1000);
    }
    void clear()
    {
        maze.clear();
        zoneInfo.clear();
        zoneMap.clear();
    }

    std::istream& read(std::istream& str)
    {
        clear();

        int r;
        int c;
        str >> r >> c;
        str.ignore(-1, '\n');

        maze.resize(r);

        std::string line;
        for(int loopY = 0; loopY < r; ++loopY)
        {
            maze[loopY].resize(c);
            for(int loopX = 0; loopX < c; ++loopX)
            {
                char v;
                str >> v;
                maze[loopY][loopX] = v - '0';
            }
        }
        return str;
    }

    int const&  loc(Point const& point) const   {return maze[point.first - 1][point.second - 1];}
    int&        loc(Point const& point)         {return maze[point.first - 1][point.second - 1];}
    char type(Point const& point) const
    {
        int l = loc(point);
        if (l < 100) {
            return l + '0';
        }
        return zoneInfo[zone(point)].getType();
    }

    int zone(Point const& point) const
    {
        int l = loc(point);
        if (l < 100) {
            return -1;
        }
        auto find = zoneMap.find(l - 100);
        return find->second;
    }

    Zone& getCurrentZone(Point const& point, Point const& dst)
    {
        int l = loc(point);
        if (l >= 100) {
            l = zoneMap[l - 100];
            zoneInfo[l].updateDestination(dst);
            return zoneInfo[l];
        }
        zoneMap[zoneInfo.size()] = zoneInfo.size();
        zoneInfo.emplace_back(type(point), zoneInfo.size(), dst);

        Zone& cZ = zoneInfo.back();
        loc(point)      = cZ.getId() + 100;
        cZ.push(point);
        return cZ;
    }

    void tryAdding(Zone& cZ, Point const& next, int v, int h)
    {
        Point point = next;
        point.first  += v;
        point.second += h;

        if (point.first <= 0 || point.first > maze.size() ||
            point.second <= 0 || point.second > maze[0].size() ||
            type(point) != cZ.getType())
        {
            return;
        }

        int l = loc(point);
        if (l < 100)
        {
            loc(point) = cZ.getId() + 100;
            cZ.push(point);
        }
        else
        {
            int currentDest = zoneMap[l - 100];
            if (currentDest != cZ.getId())
            {
                for(auto& item: zoneMap) {
                    if (item.second == currentDest) {
                        item.second = cZ.getId();
                    }
                }
                cZ.addZoneBoundry(zoneInfo[currentDest]);
            }
        }
    }

    // Basically Dijkstra algorithm,
    // Returns '0' '1' if the src and dst are the same type and can be reached.
    // returns another letter for a failure to connect.
    char route(Point const& src, Point& dst)
    {
        // The zone contains the boundry list.
        // If the src already exists in a searched zone then
        // re-use the zone and boundary list so we don't have
        // to repeat any work.
        Zone& cZ = getCurrentZone(src, dst);

        // Different types immediately fails.
        if (type(dst) != cZ.getType()) {
            return 'F';
        }

        // If we know that both points are in the same zone.
        // We don't need to expand the boundary and simply return.
        if (zone(dst) == cZ.getId()) {
            return cZ.getType();
        }

        // Otherwise expand the boundary until both
        // points are in the zone or we can't expand anymore.
        while(!cZ.empty())
        {
            Point next = cZ.top();
            if (next == dst) {
                // next location is the destination we have
                // confirmed we can get from source to dest.
                return cZ.getType();
            }

            // Only remove next if we are going to expand.
            cZ.pop();

            tryAdding(cZ, next, -1, 0);
            tryAdding(cZ, next, +1, 0);
            tryAdding(cZ, next, 0, -1);
            tryAdding(cZ, next, 0, +1);


            // This extra check is needed because
            // zones may have been combined. Thus it checks
            // to see if the two points are now in the same zone
            // after combining zones.
            if (zone(dst) == cZ.getId()) {
                return cZ.getType();
            }
        }
        return 'F';
    }

    friend std::istream& operator>>(std::istream& str, Maze& dst)
    {
        return dst.read(str);
    }
};

int main()
{
    Maze        maze;
    std::cin >> maze;

    int count;
    std::cin >> count;
    Point src;
    Point dst;
    for(int loop = 0;loop < count; ++loop)
    {
        std::cin >> src >> dst;
        switch (maze.route(src, dst))
        {
            case '0': std::cout << "binary\n";break;
            case '1': std::cout << "decimal\n";break;
            default:
                      std::cout << "neither\n";
        }
    }
}