# Matrix to Graph

```cpp
#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;

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.gomchik.com/tech/c++/matrix_to_graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.