首页 > 试题广场 > 机器人的运动范围
[编程题]机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
思路:将地图全部置1,遍历能够到达的点,将遍历的点置0并令计数+1.这个思路在找前后左右相连的点很有用,比如leetcode中的海岛个数问题/最大海岛问题都可以用这种方法来求解。

class Solution:
    def __init__(self):
        self.count = 0

    def movingCount(self, threshold, rows, cols):
        # write code here
        arr = [[1 for i in range(cols)] for j in range(rows)]
        self.findway(arr, 0, 0, threshold)
        return self.count

    def findway(self, arr, i, j, k):
        if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
            return
        tmpi = list(map(int, list(str(i))))
        tmpj = list(map(int, list(str(j))))
        if sum(tmpi) + sum(tmpj) > k or arr[i][j] != 1:
            return
        arr[i][j] = 0
        self.count += 1
        self.findway(arr, i + 1, j, k)
        self.findway(arr, i - 1, j, k)
        self.findway(arr, i, j + 1, k)
        self.findway(arr, i, j - 1, k)

发表于 2018-10-18 17:11:00 回复(7)
public class Solution {

	public int movingCount(int threshold, int rows, int cols) {
		int flag[][] = new int[rows][cols]; //记录是否已经走过
		return helper(0, 0, rows, cols, flag, threshold);
	}

	private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) {
		if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;		
		flag[i][j] = 1;
		return helper(i - 1, j, rows, cols, flag, threshold)
            + helper(i + 1, j, rows, cols, flag, threshold)
			+ helper(i, j - 1, rows, cols, flag, threshold) 
            + helper(i, j + 1, rows, cols, flag, threshold) 
            + 1;
	}

	private int numSum(int i) {
		int sum = 0;
		do{
			sum += i%10;
		}while((i = i/10) > 0);
		return sum;
	}
}

发表于 2015-08-20 15:52:20 回复(64)
/**
@author zhengyanan
@date 2017/3/14 @time 17:09
version_3:回溯法
核心思路:
1.从(0,0)开始走,每成功走一步标记当前位置为true,然后从当前位置往四个方向探索,
返回1 + 4 个方向的探索值之和。
2.探索时,判断当前节点是否可达的标准为:
1)当前节点在矩阵内;
2)当前节点未被访问过;
3)当前节点满足limit限制。
3.
运行时间:31ms
占用内存:550k
*/
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] visited = new boolean[rows][cols];
        return countingSteps(threshold,rows,cols,0,0,visited);
    }
    public int countingSteps(int limit,int rows,int cols,int r,int c,boolean[][] visited){
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || visited[r][c] || bitSum(r) + bitSum(c) > limit)  return 0;
        visited[r][c] = true;
        return countingSteps(limit,rows,cols,r - 1,c,visited)
                + countingSteps(limit,rows,cols,r,c - 1,visited)
                + countingSteps(limit,rows,cols,r + 1,c,visited)
                + countingSteps(limit,rows,cols,r,c + 1,visited)
                + 1;
    }
    public int bitSum(int t){
        int count = 0;
        while (t != 0){
            count += t % 10;
            t /= 10;
        }
        return  count;
    }
/**
@author zhengyanan
@date 2017/3/14 @time 16:26
version_2:(此段代码有问题)
核心思路:
1.本来想的是遍历每一行,找到右端第一个不能到达的点,以此为界,此界点前的点都可以到达,之后的点
机器人不可到达;
2.但后来发现,这种思路有问题,机器人可以通过上一行或者下一行的格子进入此行界点之后的格子。
经过测试,发现确实也存在这种情况。
*/
//    public int movingCount(int threshold, int rows, int cols){
//        int r,cMax, rSum,cSumMax;
//        int count = 0;
//        for (int i = 0; i < rows; i++) {
//            rSum = 0;
//            r = i;
//            while (r != 0){
//                rSum += r % 10;
//                r /= 10;
//            }
//            cSumMax = threshold - rSum;
//
//            if (cSumMax < 0)    break;
//            else{
//                int max = 0,numberOfNine,add;
//                numberOfNine = cSumMax / 9;
//                add = cSumMax % 9;
//                max = add + 1;
//                if (numberOfNine > 0){
//                    max = max * 10 + 9;
//                    numberOfNine--;
//                }
//                count += max < cols ? max : cols;
//                System.out.println(i+";"+(max < cols? max:cols));
//            }
//        }
//        return count;
//    }
/**
@author zhengyanan
@date 2017/3/13 @time 16:48
version_1:(此段代码有问题)
核心思路:
1.判断threshold 和 rows、cols 的关系,分情况讨论
(PS:题意理解错误!!!原题应该是各数位之和,而不是 行数和列数的和。)
*/
//    public int movingCount(int threshold, int rows, int cols){
//        int smaller,bigger,result;
//        smaller = rows <= cols ? rows:cols;
//        bigger = rows + cols - smaller;
//
//        result = (threshold + 1) * (threshold + 1 + 1) / 2;
//        if (threshold <= smaller){
//
//        }
//        else if (threshold > smaller && threshold <= bigger){
//            int t, differ = threshold - smaller;
//            t = differ * (1 + differ) / 2;
//            result -= t;
//        }
//        else {
//            int t = 0,differ1,differ2;
//            differ1 = threshold - smaller;
//            differ2 = threshold - bigger;
//            t += differ1 * (1 + differ1) / 2;
//            t += differ2 * (1 + differ2) / 2;
//
//            result -= t;
//        }
//        return result;
//    }

编辑于 2017-03-14 17:49:48 回复(7)
//思路:dfs,搜索四个方向,vis记录该方格是否被搜索过,
// 预判方格是否合法,合法就从该方格接着搜索  
const int MAXN=100;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};    //四个方向	
int vis[MAXN][MAXN]={0};    //记录数组
int sum;    //记录结果

class Solution {
public:
    void dfs(int x,int y,int k,int m,int n)
    {
        vis[x][y]=1;
        for(int i=0;i<=3;++i)
        {
            int newx=x+dx[i],newy=y+dy[i];
            //预判方格是否合法,合法就从该方格接着搜索 
       if(vis[newx][newy]==0&&newx>=0&&newx<m&&newy>=0&&newy<n&&(newx%10+newx/10+newy%10+newy/10<=k))
            {
                ++sum;
                dfs(newx,newy,k,m,n);
            }
        }
    }
    int movingCount(int k, int rows, int cols)
    {
        if(k<0)
            return 0;
        memset(vis,0,sizeof(vis));
        sum=1;
        dfs(0,0,k,rows,cols);
        return sum;
        
    }
};

编辑于 2017-06-03 21:54:10 回复(4)
class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        bool* flag=new bool[rows*cols];
        for(int i=0;i<rows*cols;i++)
            flag[i]=false;
        int count=moving(threshold,rows,cols,0,0,flag);//从(0,0)坐标开始访问;
        delete[] flag;
        return count;
    }
    //计算最大移动位置
    int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
    {
        int count=0;
        if(check(threshold,rows,cols,i,j,flag))
        {
            flag[i*cols+j]=true;
            //标记访问过,这个标志flag不需要回溯,因为只要被访问过即可。
           //因为如果能访问,访问过会加1.不能访问,也会标记下访问过。
            count=1+moving(threshold,rows,cols,i-1,j,flag)
                   +moving(threshold,rows,cols,i,j-1,flag)
                   +moving(threshold,rows,cols,i+1,j,flag)
                   +moving(threshold,rows,cols,i,j+1,flag);
        }
        return count;
    }
    //检查当前位置是否可以访问
    bool check(int threshold,int rows,int cols,int i,int j,bool* flag)
    {
        if(i>=0 && i<rows && j>=0 && j<cols 
            && getSum(i)+getSum(j)<=threshold 
            && flag[i*cols+j]==false)
           return true;
        return false;
    }
    //计算位置的数值
    int getSum(int number)
    {
        int sum=0;
        while(number>0)
        {
            sum+=number%10;
            number/=10;
        }
        return sum;
    }
};

编辑于 2016-08-05 18:54:33 回复(9)
动态规划 dp[i][j]表示是否可以到达,统计数字中true的个数,即为可以到达的格子数
public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0)
            return 0;
        boolean [][] dp=new boolean[rows+1][cols+1];
		dp[0][0]=true;
		for(int i=1;i<=rows;i++){//初始化
			if(dp[i-1][0]&&canreach(threshold,i,0)){
				dp[i][0]=true;
			}else {
				dp[i][0]=false;
			}
		}
		for(int i=1;i<=cols;i++){//初始化
			if(dp[0][i-1]&&canreach(threshold,0,i)){
				dp[0][i]=true;
			}else {
				dp[0][i]=false;
			}
		}
		for(int i=1;i<=rows;i++){
			for(int j=1;j<=cols;j++){
				if((dp[i-1][j]&&canreach(threshold, i, j))||(dp[i][j-1]&&canreach(threshold, i, j))){
					dp[i][j]=true;
				}else {
					dp[i][j]=false;
				}
			}
		}
		int count=0;
		for(int i=0;i<rows;i++){
			for(int j=0;j<cols;j++){
				if(dp[i][j])
					count++;
			}
		}		
	return count;       
    }
     public  boolean canreach(int threshold, int x, int y) {
	        int sum = 0;
	        while (x > 0) {
	            sum += x % 10;
	            x /= 10;
	        }
	        while (y > 0) {
	            sum += y % 10;
	            y /= 10;
	        }
	        return sum <= threshold;
	    }
}

发表于 2016-11-07 00:12:01 回复(7)
DFS
class Solution {
    bool canreach(int threshold, int x, int y) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum <= threshold;
    }
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>> grid(rows);
        for (auto& row : grid) {
            row.resize(cols, false);
        }
        queue<pair<int, int>> que;
        if (canreach(threshold, 0, 0)) {
            que.push(make_pair(0, 0));
            grid[0][0] = true;
        }
        int cnt = 0;
        while (!que.empty()) {
            ++cnt;
            int x, y;
            tie(x, y) = que.front();
            que.pop();
            if (x + 1 < rows && !grid[x + 1][y] && canreach(threshold, x + 1, y)) {
                grid[x + 1][y] = true;
                que.push(make_pair(x + 1, y));
            }
            if (y + 1 < cols && !grid[x][y + 1] && canreach(threshold, x, y + 1)) {
                grid[x][y + 1] = true;
                que.push(make_pair(x, y + 1));
            }
        }
        return cnt;
    }
};

编辑于 2015-05-06 00:01:57 回复(6)

这道是典型的DFS || BFS 题

public class Solution {

    /**算法本质:
    * DFS||BFS 寻找连通分量
    * 
     * 题目分析:
     * 机器人在一个矩阵上的m*n个格子上移动,可进入的格子的集合可抽象为以下点集:
     * { (row, col) | (i%10+i/10+j%10+j/10) <= threshold }。且路径节点可重复,无步数限制。
     * 问:机器人能到达多少个格子?
     * 
     * 题目抽象:
     * 倘若我们把矩阵的每一个“格子”抽象成一个“结点”,把“格子相邻”抽象为“结点连通”(结点之间存在无向边),
     * 把“无法进入的格子”抽象成“与所有普通结点都不连通(不存在无向边)的孤点”,则整个问题可以抽象为:
     * 从某个结点出发,寻找无向图的连通分量的节点个数。很显然,可以使用DFS或者BFS进行实现
     * 
     * 算法实现:
     * 这里选择DFS进行实现。
     * 设置两个辅助boolean矩阵:visited与isWall。前者是DFS中的典型辅助矩阵,记录每个节点是否已访问过。
     * 后者用来表示每个节点是否是不能进入的“孤点”。
     * 设置静态变量nodeCnt,用于在DFS的过程中记录访问过的结点数
     * DFS递归函数的出口条件设置为:   
     * (outOfBoundary(rows, cols, row, col) || visited[row][col] || isWall[row][col] )
     * 即:“若超过边界(到矩阵之外)”或“访问过”或“是无法进入的结点” 则 return
     * 然后进行DFS。
     * */

    int nodeCnt = 0;
    boolean[][] visited;
    boolean[][] isWall;
    int threshold;
    int rows;
    int cols;

    public int movingCount(int threshold, int rows, int cols){
        if (threshold<0 || rows<=0 || cols<=0) //robust
            return 0;//牛客示例是0

        //init
        this.nodeCnt = 0;
        this.threshold = threshold;
        this.rows = rows;
        this.cols = cols;
        this.visited = new boolean[rows][cols];
        this.isWall = new boolean[rows][cols];
        for (int i=0;i<rows;i++){
            for (int j=0;j<cols;j++){
                this.visited[i][j]=false;
                if ( (i%10+i/10+j%10+j/10) > threshold )
                    this.isWall[i][j]=true;
                else
                    this.isWall[i][j]=false;
            }
        }

        //body
        DFS(0,0);
        return this.nodeCnt;
    }

    public void DFS(int row, int col){
        if (   outOfBoundary(rows, cols, row, col) 
            || visited[row][col] 
            || isWall[row][col] )
            return;

        //visit
        visited[row][col]=true;
        nodeCnt++;

        //DFS
        DFS(row+1, col);
        DFS(row-1, col);
        DFS(row, col+1);
        DFS(row, col-1);
    }

    public boolean outOfBoundary(int rows, int cols, int row, int col){
        return ( row<0 || row>=rows || col<0 || col>=cols );
    }

}
编辑于 2018-10-25 18:49:28 回复(2)
//java简单易懂版
public class Solution {
    int count=0;
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[] pass = new boolean[rows*cols];
        movingCount(threshold,0,0,rows,cols,pass);
        return count;
    }
    public void movingCount(int threshold, int i, int j,int rows, int cols,boolean[] pass){
        int index = i*cols+j;
        if(i<0||j<0||i>=rows||j>=cols||pass[index]==true)
            return ;
        if(helper(i,j)<=threshold){
            count++;
            pass[index]=true;
        }else{
            pass[index]=false;
            return;
        }
        movingCount(threshold, i-1, j,rows,  cols,pass);
        movingCount(threshold, i+1, j,rows,  cols,pass);
        movingCount(threshold, i, j-1,rows,  cols,pass);
        movingCount(threshold, i, j+1,rows,  cols,pass);
    }
    public int helper(int i,int j){
        int sum = 0;
        do{
            sum += i%10;
        }while((i = i/10) > 0);
        
        do{
            sum += j%10;
        }while((j = j/10) > 0);
        return sum;
    }
}

发表于 2019-07-22 04:37:50 回复(0)

python solution:

class Solution:
    def movingCount(self, threshold, rows, cols):
        self.row, self.col = rows, cols
        self.dict = set()
        self.search(threshold, 0, 0)
        return len(self.dict)

    def judge(self, threshold, i, j):
        return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold

    def search(self, threshold, i, j):
        if not self.judge(threshold, i, j) or (i, j) in self.dict:
            return
        self.dict.add((i, j))
        if i != self.row - 1:
            self.search(threshold, i + 1, j)
        if j != self.col - 1:
            self.search(threshold, i, j + 1)

要注意去重:(i,j) in self.dict

如果不加这一句,时间复杂度不会满足。

编辑于 2017-10-31 23:19:29 回复(8)
public class Solution {
 
    public int movingCount(int threshold, int rows, int cols) {
       int[][] flag = new int[rows][cols];
       return moving(threshold, rows, cols, flag, 0, 0);
    }
    
    public int moving(int threshold, int rows, int cols, int[][] flag, int i, int j){
        if(threshold <= 0 || i >= rows || i< 0 || j >= cols || j < 0 || (flag[i][j] == 1) || (sum(i) + sum(j) > threshold)){
            return 0;
        }
        flag[i][j] = 1;
        return moving(threshold, rows, cols, flag, i - 1, j)
            +moving(threshold, rows, cols, flag, i + 1, j)
            +moving(threshold, rows, cols, flag, i, j - 1)
            +moving(threshold, rows, cols, flag, i, j + 1)
            + 1;    
    }
    
    public int sum(int i ){
        if(i == 0){return i ;}
        int sum = 0;
        while(i != 0){
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }

}

发表于 2015-10-19 08:43:43 回复(3)
【java】和上一题类似,本题依然用DFS来解题,依然提供递归和非递归两种方法,了解一下!
方法一:非递归
思路:不带记忆的DFS搜索 + 限定条件 = 普通的DSF例题
1.需要记录已经遍历过的节点,用辅助矩阵visited[rows * cols]
2.每次加入时,count++标记已经遍历,这样下一个节点就不会遍历了
入栈条件
1.每一位的和小于等于threshold
2.x和 y  的边界条件
3.没有遍历过
 public int movingCount(int threshold, int rows, int cols)
    {
       if(rows <= 0 || cols <= 0 || threshold < 0) return 0;
        Stack<Integer> s = new Stack<>();
        boolean[] visited = new boolean[rows * cols];
        int[][] xoy = {{0,1,0,-1},{1,0,-1,0}};
        int count = 0;
        s.add(0);
        visited[0] = true;
        while(!s.empty()) {
            int  cur = s.pop();
            count++;
            for (int i = 0; i < 4; i++) {
                int x = cur % cols + xoy[0][i];
                int y = cur / cols + xoy[1][i];
                int sum = getDigitSum(x) + getDigitSum(y);
                if(x >= 0 && x < cols && y >= 0 && y < rows 
                        && sum <= threshold && !visited[x + y * cols]) {
                    s.add(x + y * cols);
                    visited[x + y * cols] = true;
                }
            }
        }
        return count;
    }

    private int getDigitSum(int i) {//获取位的和
        int sum = 0;
        while(i > 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
方法二:递归
* 递归的方式更加简单了,比上一题简单
* 出口:
*    0:不满足边界条件 ;已经遍历过;位数和大于阈值
* 1.递:
*     1.1标记遍历
*     1.2上下左右递归
* 2.归:返回count
 public int movingCount(int threshold, int rows, int cols)
    {
        if(rows <= 0 || cols <= 0 || threshold < 0) return 0;
        boolean[] visited = new boolean[rows * cols];
        return dfs(threshold,rows,cols,visited,0,0);
    }
 private  int dfs(int threshold, int rows, int cols, boolean[] visited, int x, int y) {
        if(x < 0 || x >= cols || y < 0 || y >= rows 
                || getDigitSum(x) + getDigitSum(y) > threshold || visited[x + y * cols])
            return 0;//出口
        visited[x + y * cols] = true;//标记
        return 1 + dfs(threshold, rows, cols, visited, x, y - 1)//归
                 + dfs(threshold, rows, cols, visited, x + 1, y)
                 + dfs(threshold, rows, cols, visited, x, y + 1)
                 + dfs(threshold, rows, cols, visited, x - 1, y);
    }
private int getDigitSum(int i) {
        int sum = 0;
        while(i > 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }



编辑于 2018-06-15 21:36:10 回复(3)

利用队列宽度优先搜索
代码有点长但是很清晰

class Solution {
public:

    bool if_ok(int x, int y, int th){
        int sum = 0;
        string sx = to_string(x);
        string sy = to_string(y);
        for(int i = 0; i < sx.length();i++) sum += sx[i]-'0';
        for(int i = 0; i < sy.length();i++) sum += sy[i]-'0';
        return sum <= th;
    }


    int movingCount(int threshold, int rows, int cols){
        if(threshold <= 0) return 0;
        int stepx[4] = {1, -1, 0, 0};
        int stepy[4] = {0, 0, 1, -1};
        vector<vector<int> > dp(rows, vector<int>(cols, 0));
        queue<int> qx; queue<int> qy;
        qx.push(0); qy.push(0); dp[0][0] = 1;
        int ans = 0;
        while(!qx.empty()){
            ans++;
            int x = qx.front(); qx.pop();
            int y = qy.front(); qy.pop();
            for(int i = 0; i < 4; i++){
                if(x+stepx[i]<rows && x+stepx[i]>=0 &&
                   y+stepy[i]<cols && y+stepy[i]>=0 &&
                   if_ok(x+stepx[i],y+stepy[i],threshold) &&
                   dp[x+stepx[i]][y+stepy[i]] == 0){
                        qx.push(x+stepx[i]);
                        qy.push(y+stepy[i]);
                        dp[x+stepx[i]][y+stepy[i]] = 1;
                }
            }
        }
        return ans;
    }
};
发表于 2018-12-30 18:19:28 回复(0)
这题目不是只有两种情况吗?
 1、单行或者单列,一旦坐标数位之和小于k,之后的格子就走不到了,返回结果。 
 2、只要行列数大于等于2,除了不符合要求的格子,其他的都能访问到
 class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
       	int res = 0;
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < cols; ++j)
            	if (!bigger(threshold, i, j))
            		++res;
            	else if (rows == 1 || cols == 1)
            		return res;
        return res;
    }
    bool bigger(int num, int m, int n) {
        int sum = 0;
        while (m) {
            sum += m % 10;
            m /= 10;
        }
        while (n) {
            sum += n % 10;
            n /= 10;
        }
        return (num < sum);
    }
};
编辑于 2016-12-17 19:19:06 回复(8)

python solution:

class Solution:
    def getDigitSum(self,number):
        return sum(map(int,list(str(number))))
    def check(self,threshold,rows,cols,row,col,visited):
        if row>=0 and row<rows and col>=0 and col<cols and self.getDigitSum(row)+self.getDigitSum(col)<=threshold and not (row,col) in visited:
            return True
        return False
    def movingCountCore(self,threshold, rows, cols, row, col, visited):
        count=0
        if self.check(threshold,rows,cols,row,col,visited):
            visited.add((row,col))
            count=1+self.movingCountCore(threshold,rows,cols,row-1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col-1,visited)+self.movingCountCore(threshold,rows,cols,row+1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col+1,visited)
        return count
    def movingCount(self,threshold, rows, cols):
        # write code here
        if threshold<0 or rows<=0 or cols<=0:
            return 0
        visited=set()
        count=self.movingCountCore(threshold,rows,cols,0,0,visited)
        return count

发表于 2019-01-05 10:34:51 回复(0)
function movingCount(threshold, rows, cols)
{
    // write code here
    if(!threshold)return 1;
    if(!rows||!cols)return 0;
    var visited = [];
    var temp = [];
    var i, j;
    var count = {count:0};
    for (i = 0; i < rows; i++) {
      temp = [];
      for (j = 0; j < cols; j++) {
        temp.push(false);
      }
      visited.push(temp);
    }
    move(threshold, rows, cols, 0, 0, count, visited);
    return count.count;
}

function move(threshold, rows, cols, row, col, count, visited) {
    var isMove = false;
    if(rows>row&&cols>col&&col>=0&&row>=0&&!visited[row][col]) {
       if(bitSum(row) + bitSum(col) <= threshold) {
           visited[row][col] = true;
           count.count++;
           move(threshold, rows, cols, row+1, col, count, visited);
           move(threshold, rows, cols, row-1, col, count, visited);
           move(threshold, rows, cols, row, col-1, count, visited);
           move(threshold, rows, cols, row, col+1, count, visited);
       }
    }
    return isMove;
}

function bitSum(num) {
    var sum = 0;
    while(num) {
        sum+=num%10;
        num = parseInt(num/10)
    }
    return sum;
}

module.exports = {
    movingCount : movingCount
};

发表于 2017-08-29 12:41:03 回复(3)
//回溯法。仔细审题。。。
class Solution {
public:
	int movingCount(int threshold, int rows, int cols) {
		int res = 0;
		bool* flag = new bool[rows*cols];
		memset(flag, 0, rows*cols);
		dfs(threshold, rows, cols, flag, 0, 0, res);
		return res;
	}
	void dfs(int threshold, int rows, int cols, bool* flag, int i, int j, int &res) {
		if (i<0 || i >= rows || j<0 || j >= cols)
			return;
		if (*(flag + i*cols + j) == 1)
			return;
		if (check(i,j,threshold)){
			res++;
			*(flag + i*cols + j) = 1;
			dfs(threshold, rows, cols, flag, i, j - 1, res);//左
			dfs(threshold, rows, cols, flag, i, j + 1, res);//右
			dfs(threshold, rows, cols, flag, i - 1, j, res);//上
			dfs(threshold, rows, cols, flag, i + 1, j, res);//下
		}
	}
    bool check(int ii,int jj,int threshold){
        int sum = 0;
        while (ii != 0) {
			sum += ii % 10;
			ii = ii / 10;
		}
		while (jj != 0) {
			sum += jj % 10;
			jj = jj / 10;
		}
        return sum<=threshold;
    }
};

发表于 2017-06-28 23:14:08 回复(3)
//非递归,利用栈实现
class Solution {
public:
    int Count(int row, int col){
        int count=0;
        while(row||col){
            count+=row%10+col%10;
            row/=10;
            col/=10;
        }
        return count;
    }
    int movingCount(int threshold, int rows, int cols){
        if((rows<1&&cols<1)||threshold<0)
            return 0;
        int R=1;
        bool* visited=new bool[rows*cols];
        memset(visited,0,rows*cols);
        visited[0]=true;
        stack<int> S;
        S.push(0);
        int p[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        while(!S.empty()){
            int i=S.top()/cols,j=S.top()%cols;
            S.pop();
            for(int k=0;k<4;k++){
                int row=i+p[k][0],col=j+p[k][1];
                if(row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]&&Count(row,col)<=threshold){
                    S.push(row*cols+col);
                    visited[row*cols+col]=true;
                    R++;
				}
            }  
        }
        return R;
    }
};

发表于 2016-08-24 11:02:15 回复(2)
import java.util.*;
public class Solution {
    ArrayList<Integer> result = new ArrayList<Integer>();
    public int movingCount(int threshold, int rows, int cols)
    {
        int len = rows*cols;
        int[] state= new int[len];
            return core(threshold,0,0,state,0,rows,cols);
        
    }
    public int core(int k,int i,int j ,int[] state,int step,int rows,int cols){
        int count = 0;
        if(canIn(k,i,j ,state,step,rows,cols)){
            state[i*cols+j]=1;
            count = 1+core(k,i+1,j ,state,step,rows,cols)+core(k,i-1,j ,state,step,rows,cols)+
                core(k,i,j+1 ,state,step,rows,cols)+core(k,i,j-1 ,state,step,rows,cols);
        }
        return count;
    }
    public boolean canIn(int k,int i,int j ,int[] state,int step,int rows,int cols){
        int index = cols*i+j;
        if(i>=0&&j>=0&&i<rows&&j<cols&&state[index]!=1&&getSum(i,j)<=k){return true;}
        return false;
    }
    public int getSum(int i ,int j ){
        int sum = 0;
        while(i>0){
            sum+=i%10;
            i/=10;
        }
        while(j>0){
            sum+=j%10;
            j/=10;
        }
        return sum;
    }
}

发表于 2017-09-01 10:19:59 回复(0)
/*
思路:回溯法
把该方格看做是一个m*n的矩阵。在这个矩阵中,除边界上的各子外其他格子都有四个相邻的格子。
机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时,通过检查坐标的数位和来判断是否能进入。
如果能进入,再接着判断它能否进入四个相邻的格子(i,j-1)、(i-1,j)、(i+1,j)、(i,j+1)
 */
class Assist{
    constructor(rows,cols){
        this.visited = new Array(rows*cols);
        this.visited.fill(false);
    }
}
function movingCount(threshold, rows, cols)
{
   let assist = new Assist(rows,cols);
   let count = movingCountCore(threshold,rows,cols,0,0,assist);
   assist = null;
   return count;
}

function movingCountCore(threshold,rows,cols,row,col,assist) {
    let count = 0;
    if(check(threshold,rows,cols,row,col,assist)){
        assist.visited[row*cols+col] = true;
        count = 1+ movingCountCore(threshold,rows,cols,row-1,col,assist)
                + movingCountCore(threshold,rows,cols,row,col-1,assist)
                 + movingCountCore(threshold,rows,cols,row+1,col,assist)
                 + movingCountCore(threshold,rows,cols,row,col+1,assist);
    }
    return count;
}
function check(threshold,rows,cols,row,col,assist) {
   if(row>=0 && row < rows && col>=0 && col<cols && getDigitSum(row)+getDigitSum(col) <= threshold
        && !assist.visited[row*cols+col]){
       return true;
   }
   return false;
}

function getDigitSum(num) {
    let sum = 0;
    while (num>0){
        sum+= num%10;
        num = parseInt(num/10);
    }
    return sum;
}

发表于 2017-08-03 10:46:10 回复(1)