Matrix to Graph

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

class Cell{
    public:
        int i;
        int j;
        char val;

        Cell(){}

        Cell(int i, int j, char val): i(i), j(j), val(val){}

        string getKey(){
            return getKey(i, j);
        }

        static string getKey(int i, int j){
            return to_string(i) + "_" + to_string(j);
        }
};



class Graph{

    private:

        int M;
        int N;

        unordered_map<string, Cell*> nodes;
        unordered_map<string, vector<string> > outwardEdges;

        void addEdge(Cell* src, Cell* dst){
            outwardEdges[src->getKey()].push_back(dst->getKey());
        }


        Cell* getCell(int i, int j){
            string cellKey = Cell::getKey(i, j);
            if(nodes.find(cellKey) == nodes.end()){
                return NULL;
            }
            return nodes[cellKey];
        }


        vector<Cell*> getAllCells(){
            vector<Cell*> cells;
            for(auto kv : nodes) {
                cells.push_back(kv.second);
            }
            return cells;
        }

        void connectAdjacentCells(Cell* cell){
            Cell* upCell = getCell(cell->i - 1, cell->j);
            Cell* downCell = getCell(cell->i + 1, cell->j);
            Cell* rightCell = getCell(cell->i, cell->j + 1);
            Cell* leftCell = getCell(cell->i, cell->j - 1);

            if(rightCell){
                addEdge(cell, rightCell);
            }

            if(downCell){
                addEdge(cell, downCell);
            }

            if(leftCell){
                addEdge(cell, leftCell);
            }

            if(upCell){
                addEdge(cell, upCell);
            }

        }

        void buildGraph(vector<vector<char> >& board){
            M = board.size();
            N = board[0].size();

            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    Cell* cell = new Cell(i, j, board[i][j]);
                    // register a node
                    nodes[cell->getKey()] = cell;
                    // initialise vector to store adjacent cells of a cell
                    outwardEdges[cell->getKey()] = vector<string>();
                }
            }

            vector<Cell*> cells = getAllCells();
            for(auto cell : cells){
                connectAdjacentCells(cell);
            }
        }


    public:

        Graph(vector<vector<char> >& board){
            buildGraph(board);
        }

        bool existInSet(unordered_set<string>& set, string key){
            return set.find(key) != set.end();
        }

        bool searchUsingDfs(Cell* root, char c, unordered_set<string>& visited){
            cout << "visiting " << root->val << " (" << root->getKey() << ") " << endl;
            if(root->val == c){
                return true;
            }

            visited.insert(root->getKey());

            vector<string> adjacentCellsKeys = outwardEdges[root->getKey()];

            for(auto cellKey: adjacentCellsKeys){
                if(!existInSet(visited, cellKey)){
                    bool exist = searchUsingDfs(nodes[cellKey], c, visited);
                    if (exist)
                    {
                        return true;
                    }
                }

            }

            return false;

        }

        bool search(char c){
            Cell* root = getCell(0, 0);

            unordered_set<string> visited;

            return searchUsingDfs(root, c, visited);
        }

};



int main(){

    vector<vector<char> > board = vector<vector<char> >{
        vector<char>{'a', 'q', 'c'},
        vector<char>{'d', 'n', 'f'},
        vector<char>{'k', 't', 'p'},
    };

    Graph g(board);

    bool result = g.search('k');

    cout << "exist = " << result << endl;

}