Find all possible words given a matrix of characters.

findwords.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>

using namespace std;

struct Node {
    int r, c;
    string s;
    Node(int i, int j, string s):r(i), c(j), s(s){}
};

bool inbound(int i, int j, int m, int n) {
    return (i >= 0 && i < m && j >= 0 && j < n);
}

vector<Node> findNeighbors(const Node& node, const vector<vector<char>>& G, 
                           const vector<vector<int>>& visited, int m, int n) 
{
    int neighbors[][2] = {
        {0, 1}, {0, -1}, {-1, 0}, {1, 0}
    };
    
    vector<Node> res;
    
    for(int i=0;i<4;++i) {
        int nc = node.c + neighbors[i][0];
        int nr = node.r + neighbors[i][1];
        
        if( inbound(nr, nc, m, n) ) {
            if( visited[nr][nc] != 1 ) {
                res.push_back(Node(nr, nc, string(node.s + G[nr][nc])));            
            }
        }
    }
    
    return res;
}

set<string> solve(const vector<vector<char>>& G, int m, int n) {
    set<string> W;
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) {
            vector<vector<int>> visited(m);
            for( auto& v : visited ) v.resize(n, 0);
            
            stack<Node> S;
            S.push(Node(i, j, string(1, G[i][j])));
            visited[i][j] = 0;
            while( !S.empty() ) {
                auto cur = S.top();                
                
                if( visited[cur.r][cur.c] != 1 ) {
                    visited[cur.r][cur.c] = 1;
                    // push children
                    auto neighbors = findNeighbors(cur, G, visited, m, n);
                    for(auto n : neighbors) {
                        S.push(n);
                    }
                }
                else {
                    visited[cur.r][cur.c] = 0;
                    W.insert(cur.s);
                    S.pop();
                }
            }
        }
    }
    return W;
}

int main()
{
    ifstream fin("input.txt");
    int m, n;
    fin >> m >> n;
    vector<vector<char>> G(m);
    for(int i=0;i<m;++i) {
        G[i].resize(n);
        for(int j=0;j<n;++j) {
            fin >> G[i][j];
        }
    }

    cout << "input:" << endl;
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) {
            cout << G[i][j];
        }
        cout << endl;
    }
    
    cout << "output:" << endl;
    auto res = solve(G, m, n);
    for( auto x : res ) {
        cout << x << endl;
    }
    cout << res.size() << endl;
    return 0;
}