LeetCode 6059. 检查是否有合法括号字符串路径（BFS）

示例 1：
输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。

示例 2：
输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。
 
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 要么是 '(' ，要么是 ')' 。

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int dd = 128*128, d = 128, m = grid.size(), n = grid[0].size();
        if(grid[0][0]!='(' || grid[m-1][n-1]!=')') return false;
        vector<vector<int>> dir = {{0, 1}, {1, 0}};
        queue<int> q;
        unordered_set<int> vis;
        q.push(dd);  // 起点的编码：左括号个数*128*128 + x*128 + y
        vis.insert(dd);
        while(!q.empty())
        {
            auto tp = q.front();
            q.pop();
            int left = tp/dd;
            int x = tp%dd/d, y = tp%d;
            if(x==m-1 && y==n-1 && left==0) return true;
            for(int k = 0; k < 2; ++k)
            {
                int nx = x + dir[k][0], ny = y + dir[k][1];
                if(nx>=0 && nx<m && ny>=0 && ny<n)
                {
                    if(grid[nx][ny]=='(')
                    {
                        int hash = (left+1)*dd+(nx*d+ny);
                        if(!vis.count(hash) && left+1 <= (m-1-nx+n-1-ny))
                        {
                            q.push(hash);
                            vis.insert(hash);
                        }
                    }
                    else
                    {
                        if(left-1 < 0)  // 不能配对
                            continue;
                        int hash = (left-1)*dd+(nx*d+ny);
                        if(!vis.count(hash) && left-1 <= (m-1-nx+n-1-ny))
                        {
                            q.push(hash);
                            vis.insert(hash);
                        }
                    }
                }
            }
        }
        return false;
    }
};