剑指 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要存储所有单元格