Get co-ordinates surrounding specific matrix

Question

Given an arbitrary matrix, how do I find the co-ordinates that surrounds each city accurately? E.g. City 1 has surrounding matrix of (0, 0), (0, 3), (1, 0), (1, 3), (2,0), (2, 1), (2, 2), (2, 3).

I have tried using a hardcoded method. Which is loop through each city's co-ordinate, however there are still inaccuracy in this method. E.g. (0, 1) and from there check all 8 directions, up, down, left, right, upper left, upper right, bottom left, bottom right. And if the char value is ' ', it is not a city which means it is part of a surrounding.

Is there any way which is much more efficient and more accurate in finding the surrounding?

void surroundings(int x, int y) {
    // Initiate the first city struct information
    citySummInfo.cityId = cityLocList[0].cityId;
    citySummInfo.cityName = cityLocList[0].cityName;
    citySummInfoList.push_back(citySummInfo);

    // Add unique cityID & cityName into vector
    for (size_t i = 0; i < cityLocList.size(); i++) {
        for (size_t j = 0; j < citySummInfoList.size(); j++) {
            if (cityLocList[i].cityId == citySummInfoList[j].cityId && cityLocList[i].cityName == citySummInfoList[j].cityName) {
                break;
            }
            else if (j == citySummInfoList.size() - 1) {
                citySummInfo.cityId = cityLocList[i].cityId;
                citySummInfo.cityName = cityLocList[i].cityName;
                citySummInfoList.push_back(citySummInfo);
            }
        }
    }

    
    // To populate the entire matrix with city ID
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            for (size_t k = 0; k < cityLocList.size(); k++) {
                if (cityLocList[k].xGrid == i && cityLocList[k].yGrid == j)
                    mapPtr[j][i] = cityLocList[k].cityId + '0';
            }
        }
    }


    // Main process of getting the surrounding
    for (size_t i = 0; i < citySummInfoList.size(); i++) {
        for (size_t j = 0; j < cityLocList.size(); j++) {
            if (citySummInfoList[i].cityId == cityLocList[j].cityId)
                citySummInfoList[i].coOrdinates.push_back(to_string(cityLocList[j].xGrid) + "." + to_string(cityLocList[j].yGrid));
        }
    }

    for (size_t i = 0; i < citySummInfoList.size(); i++) {
        vector temp;
        for (size_t j = 0; j < citySummInfoList[i].coOrdinates.size(); j++) {
            char cityId = citySummInfoList[i].cityId + '0';
            char delim[] = { '.' };
            vector tempAxis = tokenizer(citySummInfoList[i].coOrdinates[j], delim, 1);

            int xAxis = stoi(tempAxis[0]);
            int yAxis = stoi(tempAxis[1]);

            if (xAxis - 1 < 0 || yAxis - 1 < 0) {
                continue;
            }

            if (mapPtr[xAxis - 1][yAxis + 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis - 1) + "." + to_string(yAxis + 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis - 1][yAxis] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis - 1) + "." + to_string(yAxis);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis - 1][yAxis - 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis - 1) + "." + to_string(yAxis - 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis][yAxis + 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis) + "." + to_string(yAxis + 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis][yAxis - 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis) + "." + to_string(yAxis - 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis + 1][yAxis + 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis + 1) + "." + to_string(yAxis + 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis + 1][yAxis] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis + 1) + "." + to_string(yAxis);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
            if (mapPtr[xAxis + 1][yAxis - 1] != cityId) {
                if (xAxis + 1 == x || yAxis + 1 == y || xAxis - 1 < 0 || yAxis - 1 < 0)
                    continue;
                string coOrd = to_string(xAxis + 1) + "." + to_string(yAxis - 1);
                if (find(temp.begin(), temp.end(), coOrd) == temp.end()) {
                    temp.push_back(coOrd);
                }
            }
        }
        citySummInfoList[i].coOrdinates.reserve(temp.size());
        citySummInfoList[i].coOrdinates.insert(citySummInfoList[i].coOrdinates.end(), temp.begin(), temp.end());
    }
}

Also, is there a possibility that my print function may cause such unreliability?

void print(int x, int y) {
    for (int i = 0; i <= x + 2; i++) {
        if (i == 0 || i >= x + 1)                                          // Indentation for 1st and last row of non city locations
            cout << setw(4) << " ";

        for (int j = 0; j <= y + 2; j++) {
            if ((i == 0 || i == x + 1) && j <= y + 1) {                         // Layout for first and last row
                cout << "# ";
            }
            else if ((j == 0 && (i != 0 || i <= x))) {                          // Numbering for each row
                if (x - i >= 0) {
                    cout << setw(3) << left << x - i << " ";
                }
                else {
                    cout << "  ";                                               // Indentation for last row of #s
                }
            }
            else if (j == 1 && i < x + 2) {                                  // Layout for first column
                cout << "#";
            }
            else if (j == y + 2 && i != 0 && i < x + 1) {                    // Layout for last column
                cout << " #";
            }
            else if (i == x + 2 && j < y + 1) {                              // Numbering for each column
                cout << j - 1 << " ";
            }
            else if ((i != 0 && i != x + 2 && j != y + 2)) {
                cout << " " << mapPtr[x - i][j - 2];                                // Plot map value
            }
        }
        cout << endl;
    }
    cout << endl;
}

user_5348875 · Answer

This is an O(n) answer for your problem. The idea behind it is to find all points that are edges (a point is an edge if it is adjacent to anything which is not its own city).

After finding all edge points, loop through each of them and add all points adjacent to them which are whitespace characters.

#include 
#define x first
#define y second
using namespace std;

typedef pair point;

string m[] = {
    "           ",
    "      555  ",
    "      555  ",
    " 222  555  ",
    " 222       ",
    " 222       ",
    " 222       ",
    "           ",
    "11  33     ",
    "11       44",
    "         44"
};

//hash function for pairs
struct hash_pair {
    template 
    size_t operator()(const pair& p) const {
        auto hash1 = hash{}(p.first);
        auto hash2 = hash{}(p.second);
        return hash1 ^ hash2;
    }
};

bool insideBounds(int x, int y, point &size){
    if(x < 0 || x >= size.x || y < 0 || y >= size.y) return false;
    return true;
}

bool isEdge(int x, int y, point &size){
    for(int i = -1; i < 2; ++i){
        for(int j = -1; j < 2; ++j){
            if(!insideBounds(x + j, y + i, size)) return true;
            if(m[y + i][x + j] == ' ') return true;
        }
    }
    return false;
}

void FindSurrounding(int x, int y){
    //size of map
    point size = make_pair(11, 11);
    //current city id
    char city = m[y][x];
    
    //finding a point in edge of the city
    point edge = make_pair(x, y);
    for(int i = x - 1; i >= 0; --i) 
        if(m[y][i] == city) edge = make_pair(i, y);
        
    //find all edge points
    unordered_set visited;
    stack toVisit;
    toVisit.push(edge);
    while(toVisit.size()){
        point current = toVisit.top();
        visited.insert(current);
        toVisit.pop();
        for(int i = -1; i < 2; ++i){
            for(int j = -1; j < 2; ++j){
                point p = make_pair(current.x + j, current.y + i);
                if(!insideBounds(p.x, p.y, size) || m[p.y][p.x] != city) continue;
                if(visited.find(p) == visited.end() && isEdge(p.x, p.y, size)){
                    toVisit.push(p);
                }
            }
        }
    }
    
    //find surrounding slots
    unordered_set surrounding;
    for (const auto& p: visited) {
        for(int i = -1; i < 2; ++i){
            for(int j = -1; j < 2; ++j){
                point curr = make_pair(p.x + j, p.y + i);
                if(insideBounds(curr.x, curr.y, size) && m[curr.y][curr.x] == ' '){
                    surrounding.insert(curr);
                }
            }
        }
    }
    
    //print answer
    for (const auto& p: surrounding) {
        cout<<"("<



OUTPUT: (2, 10), (1, 10), (2, 9), (0, 10), (2, 8), (2, 7), (1, 7), (0, 7),

Get co-ordinates surrounding specific matrix

1 Answers