剑指offer

机器人的运动范围

数组的应用和递归
package com.wang.test;

public class Myso {

    /**

     * 题目描述

     * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

     * 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

     * @param threshold 限制条件

     * @param rows 数组的总行数

     * @param cols 数组的总列数

     * @return 能达到的格子数

     */

    public static int movingCount(int threshold, int rows, int cols){

        //定义一个二维数组，标记已经访问的位置

        //1 表示已经访问了

        int[][] mark = new int[rows][cols];

        //调用移动函数，进行计算和计数，然后返回最终值

        int count  = move(threshold,rows,cols,0,0,mark);

        return count;

    }

    /**

     *

     * @param threshold 限制条件

     * @param rows 数组的总行数

     * @param cols 数组的总列数

     * @param strr 开始位置的行号 start_row

     * @param strc 开始位置的列号 start_col

     * @param mark 标记数组

     * @return 返回格子数

     */

    public static int move(int threshold, int rows, int cols,int strr,int strc,int[][] mark) {

        /*

        判断条件：

        strr<0：初始行号不能小于0

        strc<0：初始列号不能小于0

        strr>=rows ：初始行号不能大于等于整个数组的行号

        strc>=cols ：初始列号不能大于等于这个数组的列号

        mark[strr][strc] == 1 初始值为1就表示已经访问了，走到最后了，该退出函数了

        !limit(threshold,strr,strc) ：判断是否符合条件

        这个判断相当于出口

         */

        if(strr<0||strc<0||strr>=rows ||strc>=cols ||mark[strr][strc] == 1 || !limit(threshold,strr,strc)){

            return  0;

        }

        //标记初始值为1，假定的

        mark[strr][strc] = 1;

        //进行递归，开始是0，0；不需要上/左

        return 1+move(threshold,rows,cols,strr+1,strc,mark)+move(threshold,rows,cols,strr,strc+1,mark);

//                move(threshold,rows,cols,strr-1,strc,mark)+

//                move(threshold,rows,cols,strr,strc-1,mark);

    }

    /**

     * 进行判断是否符合条件

     * @param threshold 限制条件

     * @param strr 当前位置行

     * @param strc 当前位置列

     * @return 返回值为true 代表不可访问，false代表可以访问

     */

    public static boolean limit(int threshold, int strr, int strc) {

        boolean limit = true;

        //行的位数和

        int sum_row = 0;

        //列的位数和

        int sum_col = 0;

        //求行的位数和

        while(strr>0){

            sum_row += strr%10;//取出末位进行相加

            strr /= 10;//将数进行右移

        }

// 求列位数的和

        while(strc>0){

            sum_col += strc%10;

            strc /= 10;

        }

//进行判断，行的位数和+列的位数  与 限制条件进行对比

        // > 没有限制

        // < 有限制

        if(sum_col+sum_row > threshold){

            limit =false;

        }

        //返回判断结果

        return limit;

    }

    //调用进行测试

    public static void main(String[] args) {

        int i = movingCount(10,7,7);

        System.out.println(i);

    }

}
巴特西

剑指offer——2

剑指offer

最新文章

热门文章
