文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述
又到了七夕節(jié)，牛郎織女相約一起去一個(gè)n*m大小的迷宮maze里玩耍。
然而沒過多久，他們就倒霉地走散了。
現(xiàn)在給定由.,*,S,T組成的矩陣maze，
其中.表示空地,*表示障礙物,S表示牛郎的位置 ,T表示織女的位置，
牛郎和織女都會(huì)試圖尋找對(duì)方，不停地在矩陣中走動(dòng)(他們可以每次向上下左右四個(gè)方向移動(dòng)一格或者站著不動(dòng)，但是不能走到迷宮外面或者障礙物)，
請(qǐng)問他們是否有可能重逢? 如果有可能，返回True，否則返回False。

2<=n,m<=1000樣例1: 輸入: [ "S..*", "*.**", "...T" ] 輸出: true 說(shuō)明: 織女選擇不動(dòng) 牛郎行動(dòng)路線(0,0)->(0,1)->(1,1)->(2,1)->(2,2)->(2,3)樣例2: 輸入: [ "S..*", "***.", "...T" ] 輸出: false 說(shuō)明： 這兩個(gè)人無(wú)論如何和碰不上了

https://tianchi.aliyun.com/oj/338600113316063289/367781993046545028

2. 解題

class Solution { public:/*** @param maze: the maze * @return: Can they reunion?*/bool findHer(vector<string> &maze) {// Write your code herevector<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] = '*';//訪問過了，標(biāo)記下}}}return false;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的天池 在线编程 牛郎织女（广度优先搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。