文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

房間（用格柵表示）中有一個(gè)掃地機(jī)器人。
格柵中的每一個(gè)格子有空和障礙物兩種可能。

掃地機(jī)器人提供4個(gè)API，可以向前進(jìn)，向左轉(zhuǎn)或者向右轉(zhuǎn)。每次轉(zhuǎn)彎90度。

當(dāng)掃地機(jī)器人試圖進(jìn)入障礙物格子時(shí)，它的碰撞傳感器會(huì)探測(cè)出障礙物，使它停留在原地。

請(qǐng)利用提供的4個(gè)API編寫讓機(jī)器人清理整個(gè)房間的算法。

interface Robot {// 若下一個(gè)方格為空，則返回true，并移動(dòng)至該方格// 若下一個(gè)方格為障礙物，則返回false，并停留在原地boolean move();// 在調(diào)用turnLeft/turnRight后機(jī)器人會(huì)停留在原位置// 每次轉(zhuǎn)彎90度void turnLeft();void turnRight();// 清理所在方格void clean(); } 示例:輸入: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1] ], row = 1, col = 3解析: 房間格柵用0或1填充。0表示障礙物，1表示可以通過(guò)。 機(jī)器人從row=1，col=3的初始位置出發(fā)。在左上角的一行以下，三列以右。注意:輸入只用于初始化房間和機(jī)器人的位置。你需要“盲解”這個(gè)問(wèn)題。 換而言之，你必須在對(duì)房間和機(jī)器人位置一無(wú)所知的情況下，只使用4個(gè)給出的API解決問(wèn)題。 掃地機(jī)器人的初始位置一定是空地。 掃地機(jī)器人的初始方向向上。 所有可抵達(dá)的格子都是相連的，亦即所有標(biāo)記為1的格子機(jī)器人都可以抵達(dá)。 可以假定格柵的四周都被墻包圍。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/robot-room-cleaner
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

/*** // This is the robot's control interface.* // You should not implement it, or speculate about its implementation* class Robot {* public:* // Returns true if the cell in front is open and robot moves into the cell.* // Returns false if the cell in front is blocked and robot stays in the current cell.* bool move();** // Robot will stay in the same cell after calling turnLeft/turnRight.* // Each turn will be 90 degrees.* void turnLeft();* void turnRight();** // Clean the current cell.* void clean();* };*/class Solution {vector<vector<int>> dir = {{-1,0},{0,1},{1,0},{0,-1}};unordered_set<string> visited; public:void cleanRoom(Robot& robot) {visited.insert("0-0");//坐標(biāo)訪問(wèn)過(guò)dfs(robot, 0, 0, 0);}void dfs(Robot& robot, int x, int y, int d){robot.clean();int nx, ny, nd;string pos;for(int k = 1; k <= 4; ++k){ robot.turnRight();//換方向 nd = (d+k)%4;nx = x + dir[nd][0];ny = y + dir[nd][1];pos = to_string(nx)+"-"+to_string(ny);if(visited.count(pos))//下一個(gè)位置訪問(wèn)過(guò)嗎continue;if(robot.move())//沒(méi)訪問(wèn)過(guò)，可以移動(dòng)的話{visited.insert(pos);//訪問(wèn)了dfs(robot, nx, ny, nd);//移動(dòng)robot.turnRight();//回溯，調(diào)轉(zhuǎn)180度robot.turnRight();robot.move();//回退到原地robot.turnRight();//再轉(zhuǎn)180把方向調(diào)到之前走的狀態(tài)robot.turnRight();}}} };

40 ms 9.9 MB

---

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

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 489. 扫地机器人（DFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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