机器人的运动范围-剑指Offer

机器人的运动范围

题目描述

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

思路

  1. 这个跟“矩阵中的路径”那个题很相似,都是使用回溯法,不过这个题的起点是固定的,就是从(0,0)位置开始走
  2. 我们同样根据行数和列数创建一个矩阵,并且这个矩阵是包着边的矩阵,每个位置存储的是这个位置下标中每个位上的数的和,到时候直接比较即可
  3. 这个题目说的是能到达的最多的格子数,所以我们在弹栈的时候不用将结果减1,因为既然我们走过了就算“能到达”

代码

import java.util.Stack;
public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        int result = 0;
        if (threshold <= 0 || rows <= 0 || cols <= 0) {
        	return result;
        }
        int[][] data = new int[rows + 2][cols + 2];
        for (int i = 0; i < rows + 2; i++) {
        	for (int j = 0; j < cols + 2; j++) {
        		if (i == 0 || i == (rows + 1) || j == 0 || j == (cols + 1)) {
        			data[i][j] = -1;
        		} else {
        			data[i][j] = 0;
        			int rowVar = i - 1;
        			int colVar = j - 1;
        			while (rowVar > 0) {
        				data[i][j] += (rowVar % 10);
        				rowVar /= 10;
        			}
        			while (colVar > 0) {
        				data[i][j] += (colVar % 10);
        				colVar /= 10;
        			}
        		}
        	}
        }
        Stack stack = new Stack();
        boolean[][] flag = new boolean[rows + 2][cols + 2];
        for (int i = 0; i < rows + 1; i++) {
        	for (int j = 0; j < cols + 1; j++) {
        		flag[i][j] = true;
        	}
        }
        int[] init = {1, 1};
        flag[1][1] = false;
        stack.push(init);
        result++;
        while (!stack.isEmpty()) {
        	int[] temp = (int[])stack.peek();
        	int row = temp[0];
        	int col = temp[1];
        	if (data[row - 1][col] <= threshold && data[row - 1][col] > 0 && flag[row - 1][col] == true) {
        		int[] position = {row - 1, col};
        		stack.push(position);
        		flag[position[0]][position[1]] = false;
        		result++;
        	} else if (data[row][col + 1] <= threshold && data[row][col + 1] > 0 && flag[row][col + 1] == true) {
        		int[] position = {row, col + 1};
        		stack.push(position);
        		flag[position[0]][position[1]] = false;
        		result++;
        	} else if (data[row + 1][col] <= threshold && data[row + 1][col] > 0 && flag[row + 1][col] == true) {
        		int[] position = {row + 1, col};
        		stack.push(position);
        		flag[position[0]][position[1]] = false;
        		result++;
        	} else if (data[row][col - 1] <= threshold && data[row][col - 1] > 0 && flag[row][col - 1] == true) {
        		int[] position = {row, col - 1};
        		stack.push(position);
        		flag[position[0]][position[1]] = false;
        		result++;
        	} else {
        		stack.pop();
        	}
        }
        return result;
    }
}
时间: 08-03

机器人的运动范围-剑指Offer的相关文章

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了<剑指offer>,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. public class Solution { public boolean Find(int target, int [][] array) { if(array == n

【剑指Offer学习】【所有面试题汇总】

剑指Offer学习 剑指Offer这本书已经学习完了,从中也学习到了不少的东西,现在做一个总的目录,供自已和大家一起参考,学如逆水行舟,不进则退.只有不断地学习才能跟上时候,跟得上技术的潮流! 所有代码下载[https://github.com/Wang-Jun-Chao/coding-interviews] 目录 第01-10题 [剑指Offer学习][面试题02:实现Singleton 模式--七种实现方式] [剑指Offer学习][面试题03:二维数组中的查找] [剑指Offer学习][面

剑指offer算法总结

剑指offer算法学习总结 节选剑指offer比较经典和巧妙的一些题目,以便复习使用.一部分题目给出了完整代码,一部分题目比较简单直接给出思路.但是不保证我说的思路都是正确的,个人对算法也不是特别在行,只不过这本书的算法多看了几遍多做了几遍多了点心得体会.于是想总结一下.如果有错误也希望能指出,谢谢. 具体代码可以参考我的GitHub仓库: https://github.com/h2pl/SwordToOffer 数论和数字规律 从1到n整数中1出现的次数 题目描述 求出1~13的整数中1出现的

LeetCode题解分类汇总(包括剑指Offer和程序员面试金典,持续更新)

LeetCode题解汇总(持续更新,并将逐步迁移到本博客列表中) 剑指Offer 数据结构 链表 序号 题目 难度 06 从尾到头打印链表 简单 18 删除链表的节点 简单 22 链表中倒数第k个节点 简单 二叉树 序号 题目 难度 07 重建二叉树 中等 栈和队列 序号 题目 难度 09 用两个栈实现队列 简单 图 序号 题目 难度 12 矩阵中的路径 中等 13 机器人的运动范围 中等 算法 动态规划 序号 题目 难度 10- I 斐波那契数列 简单 10- II 青蛙跳台阶问题 简单 查找

剑指Offer——银行考试

剑指Offer--银行考试 网申简历 一. 银行网申简历主要看哪些方面? 1.职业形象(30%),基本体现为证件照: 2.学校+成绩+校内表现(40%),体现为证书,成绩排名以及任职经历等: 3.校外实践(20%),主要体现在工作实习.实践活动和培训经历三点: 4.其他(10%),根据简历的完整性.准确性,进行综合评定. 二.网申简历应注意哪些方面? 1.考虑银行人的思维习惯(考虑岗位匹配度) 例:申请职位为柜员时,就应该在简历中体现出热情.乐于帮助他人.沉稳细心.认真大方,具有服务意识且对数字

【剑指offer】Q38:数字在数组中出现的次数

与折半查找是同一个模式,不同的是,在这里不在查找某个确定的值,而是查找确定值所在的上下边界. def getBounder(data, k, start, end, low_bound = False): if end < start : return -1 while start <= end: mid = ( start + end ) >> 1 if data[ mid ] > k: end = mid - 1 elif data[ mid ] < k: star

【剑指offer】树的子结构

转载请注明出处:http://blog.csdn.net/ns_code/article/details/25907685 剑指offer第18题,九度OJ上测试通过! 题目描述: 输入两颗二叉树A,B,判断B是不是A的子结构. 输入: 输入可能包含多个测试样例,输入以EOF结束.对于每个测试案例,输入的第一行一个整数n,m(1<=n<=1000,1<=m<=1000):n代表将要输入的二叉树A的节点个数(节点从1开始计数),m代表将要输入的二叉树B的节点个数(节点从1开始计数).

【剑指offer】二叉树的镜像

转载请注明出处:http://blog.csdn.net/ns_code/article/details/25915971 题目描述: 输入一个二叉树,输出其镜像. 输入: 输入可能包含多个测试样例,输入以EOF结束.对于每个测试案例,输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数(节点从1开始编号).接下来一行有n个数字,代表第i个二叉树节点的元素的值.接下来有n行,每行有一个字母Ci.Ci='d'表示第i个节点有两子孩子,紧接着是左孩子编号和右孩子编号.C

【剑指offer】数组中仅仅出现一次的数字(1)

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27649027 题目描写叙述: 一个整型数组里除了两个数字之外,其它的数字都出现了两次.请敲代码找出这两个仅仅出现一次的数字. 输入: 每一个測试案例包括两行: 第一行包括一个整数n,表示数组大小.2<=n <= 10^6. 第二行包括n个整数,表示数组元素,元素均为int. 输出: 相应每一个測试案例.输出数组中仅仅出现一次的两个数.输出的数字从小到大的顺序. 例子输入: 8 2 4