矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

class Solution {
public:
    vector<vector<char>> g;
    int m, n;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    bool in (int x, int y) {
        return 0 <= x && x < m && 0 <= y && y < n;
    }

    bool dfs (int x, int y, int u, string& s) {
        if (g[x][y] != s[u]) return false;
        if (u == s.size() - 1) return true;

        char c = g[x][y];
        g[x][y] = '*';
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (in(tx, ty) && g[tx][ty] != '*') {
                if (dfs(tx, ty, u + 1, s)) {
                    return true;
                }
            }
        }
        g[x][y] = c;

        return false;
    }

    bool hasPath(vector<vector<char>>& g_, string s) {
        g = g_;
        if (!g.size() || !g[0].size()) return false;
        m = g.size(), n= g[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs (i, j, 0, s)) return true;
            }
        }

        return false;
    }
};