[基础算法] DFS算法求解机器人位置移动

[基础算法] DFS算法求解机器人位置移动

【问题】地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

算法分析：

算法代码

package com.bean.algorithmbasic;

public class RobotMoving {

	public static int movingCount(int threshold, int rows, int cols) {
	
		// 变量初始化
		int[][] visited = new int[rows][cols];
		for (int i = 0; i < visited.length;i++) {
			for(int j=0;j<visited[0].length;j++) {
				visited[i][j]=0;
			}
		}
		return DFS(0,0,rows,cols,visited,threshold);
	}


	private static int DFS(int x, int y, int rows, int cols, int[][] visited,int threshold ) {

		if(x<0||y<0||x>=rows||y>=cols||visited[x][y]==1||getDigitSum(x)+getDigitSum(y)>threshold) {
			return 0;
		}
		
		visited[x][y]=1;

		return DFS(x+1,y,rows,cols,visited,threshold)+
			   DFS(x-1,y,rows,cols,visited,threshold)+
			   DFS(x,y+1,rows,cols,visited,threshold)+
			   DFS(x,y-1,rows,cols,visited,threshold)+1;
	}


	/**
	 * 一个数字的数位之和
	 *
	 * @param number  数字
	 * @return 数字的数位之和
	 */
	private static int getDigitSum(int number) {
		int result = 0;
		while (number > 0) {
			result += (number % 10);
			number /= 10;
		}

		return result;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int RESULT = movingCount(3,4,6);
		System.out.println("RESULT = "+RESULT);
	}

}

计算结果：

RESULT = 10

[基础算法] DFS算法求解机器人位置移动

相关推荐