劍指 Offer 13. 機器人的運動範圍（中等）

思路：

典型的dfs（深度優先）、bfs（廣度優先）題目

代碼：

class Solution {
	int m,n,res=0;
	int[][] dirs={{0,1},{1,0}};
	//這裡不能像之前一樣，設字元串為'/0'來作為已通路
	boolean[][] visited;
	
    public int movingCount(int m, int n, int k) {
		//在這裡才執行個體化，前面的m和n是形參
		this.visited=new boolean[m][n];
		
		this.m=m;
		this.n=n;
		
		dfs(0,0,k);
		return res;
    }
	
	private void dfs(
					int row,
					int col,
					int k
					
	){
		if(!inArea(row,col)||visited[row][col]){
			return;
		}
		
		if(row/10+row%10+col/10+col%10<=k){
			res++;
			visited[row][col]=true;
			
			//隻向2個方向搜尋即可(下、右)
			for(int i=0;i<2;i++){
				int newRow=row+dirs[i][0];
				int newCol=col+dirs[i][1];
	
				dfs(newRow,newCol,k);
					
				
			}
		
		}

	}
	
	private boolean inArea(int x,int y){
		if(x>=0&&x<m&&y>=0&&y<n){
			return true;
		}
		else{
			return false;
		}
	}
}
           

分解：

1）此題有一點不一樣的是：将個别變量設定為全局變量（m、n、visited、res、dirs）

2）剪枝有兩個if：

    i）if(!inArea(row,col)||visited[row][col])

    ii）if(row/10+row%10+col/10+col%10<=k)

① 行列索引越界 、 ② 數位和超出目标值 

k

、 ③ 目前元素已通路過

3）此題隻搜尋2個方向，右和下。因為是從{0,0}開始走的

複雜度分析：

時間複雜度：O（M*N）最差情況下，要周遊所有單元格

空間複雜度：O（M*N）最差情況下，visited要存儲所有單元格