问10种人

EN

#include 
#include 
#include 
#include 
#include 
#include 

struct Point: public std::pair
{
    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          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>   maze;
    std::vector               zoneInfo;
    std::map              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";
        }
    }
}