10 Kinds of People Open Kattis Problem Time Limit Exceeded C++

Question

I am trying to solve the open kattis problem '10 kinds of people' (https://open.kattis.com/problems/10kindsofpeople) using a best-first search algorithm and c++.

10 Kinds of People

The world is made up of 10 kinds of people, those who understand binary and those who do not. These different kinds of people do not always get along so well. Bob might ask for a 10000 ounce coffee (meaning binary) and Alice might make misinterpret his request as being in decimal and give him a 10011100010000 ounce coffee (binary). After Sue explains that this much coffee costs 100 dollars (decimal), Bob might assume he only has to pay 4 dollars (interpreting the price as being in binary). In response to these differences that are difficult to resolve, these two groups have divided the world into two regions, the binary-friendly zones and the decimal-friendly zones. They have even published a map like the following to help people keep up with where the areas are (they have used ones and zeros so nobody would have trouble reading it).
1111100000
1111000000
1110000011
0111100111
0011111111

Users of binary have to stay in the zones marked with a zero. Users of decimal have to stay in the zones marked with a one. You have to figure out if it is possible for either type of person to get between various locations of interest. People can move north, south, east or west, but cannot move diagonally.

Input

Input starts with a line containing two positive integers, 1 ≤ r ≤1000 and 1 ≤ c ≤ 1000. The next r input lines give the contents of the map, each line containing exactly c characters (which are all chosen from 0 or 1). The next line has an integer 0≤n≤1000. The following n lines each contain one query, given as four integers: r1,c1 and r2,c2. These two pairs indicate two locations on the map, and their limits are 1 ≤ r1, r2 ≤r and 1 ≤ c1, c2 ≤c.

Output

For each query, output binary if a binary user can start from location r1, c1 and move to location r2,c2. Output decimal if a decimal user can move between the two locations. Otherwise, output neither.

The task is to find if there is a path between the start and end points on a map for a given set of problems.

I initially tried using just BFS but got the TLE error, then I tried using the manhattan distance heuristic and selecting the best frontier first. To save time I am checking if the start and end node are of the same type before running the algorithm, if they are not there will be no path. I also use a map containing information about each node to avoid looping through the frontier and visited vectors for simple checks. However I still get the TLE error.

I would really like some input on what I can do to optimize my code below, or what your thoughts are. Thank you very much.

    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #include <deque>

    using namespace std;

    struct map_node {
        bool in_visited = false;
        bool in_frontier = false;
    };

    void read_input(vector<vector<char>>& map, vector<pair<unsigned, unsigned>>& start_points, vector<pair<unsigned, unsigned>>& end_points) {
        //read map
        int r = 0, c = 0;
        cin >> r >> c;
        char val;
        map.resize(r);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> val;
                map.at(i).push_back(val);
            }
        }
        //read start and end coordinates
        int n = 0;
        cin >> n;
        int r1, c1, r2, c2;
        for (int i = 0; i < n; i++) {
            cin >> r1 >> c1 >> r2 >> c2;
            start_points.push_back(make_pair(r1 - 1, c1 - 1));
            end_points.push_back(make_pair(r2 - 1, c2 - 1));
        }
    }

    int manhattan_distance(pair<unsigned int, unsigned int> node, pair<unsigned int, unsigned int> end_point) {
        int x_distance = end_point.first - node.first;
        x_distance = abs(x_distance);
        int y_distance = end_point.second - node.second;
        y_distance = abs(y_distance);
        return x_distance + y_distance;
    }

    pair<unsigned int, unsigned int> select_best_from_frontier_and_pop(deque<pair<unsigned int, unsigned int>>& frontiers, pair<unsigned int, unsigned int> end_point) {
        int lowest = manhattan_distance(frontiers.at(0), end_point);
        deque<pair<unsigned int, unsigned int>>::iterator best_node = frontiers.begin();

        for (deque<pair<unsigned int, unsigned int>>::iterator it = frontiers.begin(); it != frontiers.end(); ++it)
        {
            int score = manhattan_distance(*it, end_point);
            if (score < lowest) {
                lowest = score;
                best_node = it;
            }
        }
        pair<unsigned int, unsigned int> temp = *best_node;
        frontiers.erase(best_node);
        return temp;
    }

    vector <pair<unsigned, unsigned>> predecessors(vector<vector<char>> map, pair<unsigned int, unsigned int> node) {
        vector <pair<unsigned, unsigned>> predecessors;
        //binary if map value is 0 else decimal
        char check_val = map.at(node.first).at(node.second);
        //check left
        if (node.second > 0) {
            if (map.at(node.first).at(node.second - 1) == check_val)
                predecessors.push_back(make_pair(node.first, node.second - 1));
        }
        //check right
        if (node.second < map.at(0).size() - 1) {
            if (map.at(node.first).at(node.second + 1) == check_val)
                predecessors.push_back(make_pair(node.first, node.second + 1));
        }
        //check down
        if (node.first < map.size() - 1) {
            if (map.at(node.first + 1).at(node.second) == check_val)
                predecessors.push_back(make_pair(node.first + 1, node.second));
        }
        //check up
        if (node.first > 0) {
            if (map.at(node.first - 1).at(node.second) == check_val)
                predecessors.push_back(make_pair(node.first - 1, node.second));
        }
        return predecessors;
    }

    string solve(vector<vector<char>> map, pair<unsigned, unsigned> start, pair<unsigned, unsigned> end) {
        deque<pair<unsigned int, unsigned int>> frontiers;
        std::map<pair<int, int>, map_node> map_nodes;

        frontiers.push_back(start);
        map_nodes[{start.first, start.second}].in_frontier = true;

        vector<pair<unsigned int, unsigned int>> visited;

        while (true) {
            //fail
            if (frontiers.size() == 0)return "neither";

            //get and pop first in frontiers
            pair<unsigned int, unsigned int> node = select_best_from_frontier_and_pop(frontiers, end);
            visited.push_back(node);
            map_nodes[{node.first, node.second}].in_frontier = false;
            map_nodes[{node.first, node.second}].in_visited = true;

            //goal test
            if (node.first == end.first && node.second == end.second) {
                if (map.at(end.first).at(end.second) == '0') {
                    return "binary";
                }
                else {
                    return "decimal";
                }
            }

            //for each predecessor
            for (const auto &next : predecessors(map, node)) {
                if (map_nodes[{next.first, next.second}].in_frontier == false && map_nodes[{next.first, next.second}].in_visited == false) {
                    frontiers.push_back(next);
                    map_nodes[{next.first, next.second}].in_frontier = true;
                }
            }
        }
    }

    int main() {
        vector<vector<char>> map;
        vector<pair<unsigned, unsigned>> start_points;
        vector<pair<unsigned, unsigned>> end_points;
        read_input(map, start_points, end_points);

        for (size_t i = 0; i < start_points.size(); i++) {
            if (map[start_points.at(i).first][start_points.at(i).second] == map[end_points.at(i).first][end_points.at(i).second]) {

                cout << solve(map, start_points.at(i), end_points.at(i)) << endl;
            }
            else {
                cout << "neither" << endl;
            }
        }
    }

Answer 1

Most obvious optimizations - check if start point and end point are the same. If they are differs then neither of citizens can move.

Second - flatten your map. You can have just one contiguous vector size of r*c elements and points can be "flattened" to index as point.x + width * point.y. So flattening map allows you to flatten your start points and end points as well. This will shorten memory print overall.

Instead of BFS with deque use A* priority_queue with the same manhattan heuristic as priority. It will walk less cells when paths exists. Also use set for points you've already visited instead of vector. As even further improvement you can try to make bidirectional and search from both ways.

predecessors function do allocations on every tick. it's better if you have reserved vector and just update it's content, not create it anew. something like

//somewhere up
vector& pred;
pred.reserve(4);// nwse points
...
void predecessors(vector& pred, point pos) {
   pred.clear();// zeroes memory
   if (check1) pred.push_back(point);
   if (check2) pred.push_back(point);
   if (check3) pred.push_back(point);
   if (check4) pred.push_back(point);
}

where checks are just comparing value of current pos and surrounding points.

also for simplifying code introduce some simple Point struct instead of pair and add to_index helper and operator+ to it. point+Point{1,0}; is way cleaner then make_pair(point.first+1, point.second);

Answer 2

The task is to find if there is a path between the start and end points on a map for a given set of problems.

That's the key to doing this efficiently: all you need to do is figure out if a path exists, you don't need to find out what that path is.

An easy way to do this is to color the map: load the map into memory, then use the flood fill algorithm of your choice (complexity O(N)) to convert each cluster of 1s or 0s into some other number. For ease of distinguishing binary regions from decimal regions, I'd use even numbers for binary regions and odd numbers for decimal regions.

Once you've done that, finding the existence of a path is simply a matter of checking the color of the endpoints. If the endpoints have the same color, travel is possible; if they don't, it isn't.