劍指 Offer 13. 機(jī)器人的運(yùn)動范圍

思路一：利用dfs深度優(yōu)先搜索

• 首先確定遞歸搜索的終止條件

  1：i，j超出范圍

  2：數(shù)位之和大于k

  3：(i,j)被訪問過

• 接下來進(jìn)行dfs

  可以進(jìn)行一個dfs減枝優(yōu)化，由于從0，0開始，則只要判斷右邊和下邊即可，因為左和上一定會在搜索過程中被包括

class Solution { public:// set<vector<int>> visited; //用來存訪問過的數(shù)//獲取行列坐標(biāo)之和int getSum(int i,int j){int resall=0;while(i){ //當(dāng)為0時候退出循環(huán)resall += i%10; //求最后一位余數(shù)i/=10; //去除最后一位}while(j){resall += j%10; //求最后一位余數(shù)j/=10; //去除最后一位}return resall;}int dfs(int i,int j,int m,int n,int k,vector<vector<bool>>& flag){ //寫一個深度優(yōu)先遍歷// vector<int> temp={i,j};//確定dfs終止條件//1:i,j超范圍 i>=m||j>=n//2:數(shù)位和大于k getSum(i,j)>k//3:i,j的坐標(biāo)被訪問過 visited.find(temp)!=visited.end()if(i>=m||j>=n||getSum(i,j)>k||flag[i][j]){return 0;}// visited.insert(temp);flag[i][j] = true;//如果從(0,0)開始不用考慮向上移動的,沒有回溯int res = 1 + dfs(i+1,j,m,n,k,flag) +dfs(i,j+1,m,n,k,flag);return res;}int movingCount(int m, int n, int k) {vector<vector<bool>> flag(m, vector<bool>(n, false));int res=0;res = dfs(0,0,m,n,k,flag);return res;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-剑指 Offer 13. 机器人的运动范围的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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