1. 题目
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。
如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
- 字符串是
()。 - 字符串可以表示为
AB（A 连接 B），A 和 B 都是合法括号序列。 - 字符串可以表示为
(A)，其中 A 是合法括号序列。
给你一个 m x n 的括号网格图矩阵 grid 。
网格图中一个 合法括号路径 是满足以下所有条件的一条路径：
- 路径开始于左上角格子
(0, 0)。 - 路径结束于右下角格子
(m - 1, n - 1)。 - 路径每次只会向 下 或者向 右 移动。
- 路径经过的格子组成的括号字符串是 合法 的。
如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。
示例 1：
输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。
示例 2：
输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 要么是 '(' ，要么是 ')' 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 使用队列进行广度优先搜索
- 队列里存储
{ 待配对的左括号个数，位置信息x， y }，将3个值编码成一个 int
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;
}
};
1556 ms 282.6 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
