10 Kinds of People

Follow up to this question: 10 Kinds of People Open Kattis Problem Time Limit Exceeded C++

Solves the puzzle linked in that question.

I use Dijkstra algorithm to find items.
The only twist is that each time I do a search I save the boundary list of the search in a Zone. On a subsequent search if my current "Zone" bumps into an existing Zone I merge the boundary lists and make the old zone point at the current zone.

The searched squares are stored directly on the map 0 or 1 mean original value while any value >= 100 means a zone number (subtract 100 to get the zone). You can then use this value in the zoneMap (if zones clide this keeps the mapping upto date) to get the zone it belongs to.

I tried A* but for a problem space this small it doubles the time as you need to keep an ordered list to know which item to search for next. You can see the remininest of the A* stuff in the Zone class as commented out parts to keep the boundary list sorted.

#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 << "binaryn";break;
            case '1': std::cout << "decimaln";break;
            default:
                      std::cout << "neithern";
        }
    }
}