Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
876 B
0
Indexable
Never
    vector<string> findPath(vector<vector<int>> &m, int n) {
        vector<string> paths;
        findPathUtil(m, n, 0, 0, paths, "");
        return paths;
    }
    
    void findPathUtil(vector<vector<int>> &m, int n, int i, int j, 
    vector<string> &paths, string path) {
        if (i < 0 || j < 0 || i >= n || j >= n 
            || m[i][j] == 0 || m[i][j] == 2) // m[i][j] == 2 means visited
            return;
            
        if (i == n-1 && j == n-1) {
            paths.push_back(path);
            return;
        }
            
        m[i][j]++; // m[i][j] == 2 means visited
        findPathUtil(m, n, i, j-1, paths, path + 'L');
        findPathUtil(m, n, i, j+1, paths, path + 'R');
        findPathUtil(m, n, i-1, j, paths, path + 'U');
        findPathUtil(m, n, i+1, j, paths, path + 'D');
        m[i][j]--; // m[i][j] == 1 means not visited
    }