天池 在线编程 牛郎织女（广度优先搜索）

2<=n,m<=1000

样例1:
输入: 
[
"S..*",
"*.**",
"...T"
]
输出: true
说明:
织女选择不动
牛郎行动路线(0,0)->(0,1)->(1,1)->(2,1)->(2,2)->(2,3)

样例2:
输入:
[
"S..*",
"***.",
"...T"
]
输出: false
说明：
这两个人无论如何和碰不上了

class Solution {
public:
    /**
     * @param maze: the maze 
     * @return: Can they reunion?
     */
    bool findHer(vector<string> &maze) {
        // Write your code here
        vector<vector<int>> dir = {{0,1},{1,0},{-1,0},{0,-1}};
        queue<pair<int,int>> q;
        int m = maze.size(), n = maze[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(maze[i][j]=='S')
                {
                    q.push({i,j});
                    maze[i][j] = '*';
                    break;
                }
        while(!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny]!='*')
                {
                    q.push({nx, ny});
                    if(maze[nx][ny]=='T')
                        return true;
                    maze[nx][ny] = '*';//访问过了，标记下
                }
            }
        }
        return false;
    }
};