1. 題目

一個機器人位于一個m*n的網格的左上角。
機器人可以在任何時間點移動任何方向，但是每個網格只能達到一次。機器人正試圖到達網格的右下角。
有多少種可能的獨特路徑?

樣例 1: 輸入: 2 3 輸出: 4樣例 2: 輸入: 3 3 輸出: 12

2. 解題

• 暴力回溯即可

class Solution {int sum = 0;int r,c;vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}}; public:int uniquePaths(int m, int n) {if(m==0 || n==0)return 0;r= m, c= n;vector<vector<int>> map(m,vector<int>(n,1));map[0][0] = 0;//標記走過dfs(map,0,0);return sum;}void dfs(vector<vector<int>>& map, int i, int j){if(i==r-1 && j==c-1){sum++;return;}int x, y;for(int k = 0; k < 4; ++k){x = i+dir[k][0];y = j+dir[k][1];if(x>=0 && x<r && y>=0 && y<c && map[x][y]){map[x][y]=0;//標記走過dfs(map,x,y);map[x][y]=1;//回溯}}} };

100% 數據通過測試
總耗時 101 ms
您的提交打敗了 81.90% 的提交!

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LintCode 795. 4种独特的路径（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。