2267. 检查是否有合法括号字符串路径

    int mem[100][100][100][100];

class Solution {
public:
    // 0 unknow
    // 1 true
    // 2 false
    bool dfs(const vector<vector<char>>& grid, int x1, int y1, int x2, int y2) {
        if (x1 >= grid.size() || x2 >= grid.size() || y1>=grid[0].size() || y2 < 0 || x2 < 0 || x1 > x2 || y1 > y2) 
            return false;
        if ((x2 - x1 + y2 - y1)%2==0) return false;

        if (mem[x1][y1][x2][y2] != 0) {
            return mem[x1][y1][x2][y2] == 1;
        }
        if ( x2 - x1 + y2 - y1 == 1 && grid[x1][y1] == '(' && grid[x2][y2] == ')') {
            mem[x1][y1][x2][y2] = 1;
            return true;
        }
        
        if (grid[x1][y1] == '(' && grid[x2][y2] == ')'){
        bool tmp = dfs(grid, x1+1, y1, x2-1, y2) ||
        dfs(grid, x1+1, y1, x2, y2-1) ||
        dfs(grid, x1, y1+1, x2-1, y2) ||
        dfs(grid, x1, y1+1, x2, y2-1);
        if (tmp) {
            mem[x1][y1][x2][y2] = 1;
            return true;
        }

        for (int i=x1; i<=x2; ++i) 
            for (int j=y1; j<=y2; ++j) {
                if (i == x1 && j==y1) continue;
                if (i == x2 && j==y2) continue;
                if ((dfs(grid, x1, y1, i, j) && dfs(grid, i, j+1, x2, y2))) {
                    mem[x1][y1][x2][y2] = 1;
                    return true; 
                }
                if (dfs(grid, x1, y1, i, j) && dfs(grid, i+1, j, x2, y2)) {
                    mem[x1][y1][x2][y2] = 1;
                    return true; 
                }
            }
        mem[x1][y1][x2][y2] = 2;
        return false;
        }
        else {
                    mem[x1][y1][x2][y2] = 2;
            return false;
        }
    }


    bool hasValidPath(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        if ((row + col)%2==0) return false;
        
        if ( grid[0][0] == ')' || grid[row - 1][col - 1] == '(') return false;

        memset(mem, 0, sizeof mem);
        return dfs(grid, 0, 0, row-1, col -1);
    }
};

class Solution {
public:
    bool hasValidPath(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false; // 剪枝
        bool vis[m][n][(m + n + 1) / 2]; memset(vis, 0, sizeof(vis));
        function<bool(int, int, int)> dfs = [&](int x, int y, int c) -> bool {
            if (c > m - x + n - y - 1) return false; // 剪枝：即使后面都是 ')' 也不能将 c 减为 0
            if (x == m - 1 && y == n - 1) return c == 1; // 终点一定是 ')'
            if (vis[x][y][c]) return false; // 重复访问
            vis[x][y][c] = true;
            c += grid[x][y] == '(' ? 1 : -1;
            return c >= 0 && (x < m - 1 && dfs(x + 1, y, c) || y < n - 1 && dfs(x, y + 1, c)); // 往下或者往右
        };
        return dfs(0, 0, 0);
    }
};