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<string> temp;
        for (size_t j = 0; j < citySummInfoList[i].coOrdinates.size(); j++) {
            char cityId = citySummInfoList[i].cityId + '0';
            char delim[] = { '.' };
            vector<string> 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;
}

Answer 1

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 <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> point;

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

//hash function for pairs
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(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<point, hash_pair> visited;
    stack<point> 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<point, hash_pair> 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<<"("<<p.x<<", "<<p.y<<"), ";
    }
}

int main()
{
    FindSurrounding(0, 8);
    return 0;
}

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