剑指offer机器人运动范围 JZ66

目录

本文是参考牛客网的官方题解结合自己理解写的，官方题解：牛客官方题解
其中官方题解采用C++,博主已入JAVA坑,理解官方题解意思,使用JAVA写的

题目描述

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

题目理解

给定一个矩阵的行和列row，columns和阈值threshold，从(0,0)出发，每次可以往上下左右四个方向走，并且走到(i,j)时，i和j的每位数之和需要小于等于threshold，问最多可以走多少格子。
对于这种遍历,我们首先可以想到深度优先搜索(DFS)或者广度优先搜索(BFS),当满足条件的进行标记,依次遍历完所有节点

方法一：DFS遍历

根据题目描述，我们可以模拟题目，我们假设一个5x5矩阵，阈值threshold=3，如果我们用DFS的话，就是按照某一个分支进行访问，而这种分支访问一般是采用递归的方式进行实现,对于DFS大家最好先理解递归,可以先看我上一篇剪绳子的题,就是一个很典型的递归.我在下面画了一个图,按照对应的方向进行搜索.

最开始，我们在(0,0)的位置，我们假设按照{右，上，左，下}的方向去试探。所以我们走的顺序应该是按照图中的下标走的。
当走到4的时候，发现不能往继续往右边走，并且4个方向都走不通了，那就回溯到3,发现可以走到5，接着就站在5的视角，发现可以走6，就一直按照这个想法。

本题的递归函数就是：首先站在(0,0)的视角，先往右试探，发现可以走，就以下一个为视角，继续做相同的事情

package JZ66_Robot_move;
import java.util.Scanner;
import java.util.Arrays;
/*
 * DFS深度优先,Depth First Search 对每一个可能的分之路径深入到不能深入为止
 * 且每个节点只能访问一次,同时做相应标记,当访问到该分支路径的末尾节点,就回溯到上一个节点,站在这个节点再进行四个方向的探索
 * 假设有一个5*5的矩阵,我们用DFS,就是一直按照一个方向走,假设我们按照{右,上,左,下}的方向试探,
 * 就是先按照向右一直搜索,当位置大于阈值就回溯到前面的位置在向下一直搜索
 * 第一步，检查下标
 *  第二步：检查是否被访问过，或者是否满足当前匹配条件
 *  第三步：检查是否满足返回结果条件
 *  第四步：都没有返回，说明应该进行下一步递归
 *  标记
 *  dfs(下一次)
 *   回溯
 */
public class Dfs_Move {
	/*四个方向
	 * x+dir[i+1] y+dir[i]
	 * x+0 y+1 右
	 * x-1 y+0 上
	 * x+0 y-1 左
	 * x+1 y+0 下
	 * 想把右,下,左,上排列出来,但是尝试了下,会出现重复
	*/
	public int[] dir= {1, 0 ,-1 ,0 ,1};
	public static  int  count=0;
	//下表转化 如35转成5+3=8
	public  int  check(int n) {
		int sum=0;
		while(n>0) {
			sum+=(n%10);
			n/=10;
		}
		return n;
	}
    public void  dfs(int x,int y,int threshold,int rows,int columns,int[][] mark) {
    	//检查下标
    	if(x<0||x>=rows||y<0||y>=columns) {
    		return ;
    	}
    	//必须分开,不然数组越界会报错
    	if(mark[x][y]==1) {
    		return ;
    	}
    	int sum_xy=check(x)+check(y);
    	//检查坐标之和是否大于阈值
    	if(sum_xy>threshold) {
    	    return ;
    	}
    	//此时经过检查 坐标[x] [y]是满足条件的
    	mark[x][y]=1;
    	count+=1;
    	//进行下一步的递归,按照右下左上的方向试探
    	for(int i=0;i<4;i++) {
    		dfs(x+dir[i+1],y+dir[i],threshold,rows,columns,mark);
    	}
    }
    public static void main(String[] args) {
    	System.out.print("Enter a row:"); 
    	Scanner sc=new Scanner(System.in);
        int rows=sc.nextInt();
        System.out.println("Enter a columns:");
        int columns=sc.nextInt();
        System.out.println("Enter a threshold:"); 
        int threshold=sc.nextInt();
        int[][] mark=new int[rows][columns];
        for(int i=0;i<rows;i++) {
        	for(int j=0;j<columns;j++) {
        		mark[i][j]=0;
        	}
        }
        Dfs_Move a=new Dfs_Move();
        a.dfs(0,0,threshold,rows,columns,mark);
        System.out.println(count);
    }
}

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)

方法二：BFS遍历

当前图的遍历算法还有广度优先搜索(BFS)，所以也可以用BFS做。方法一实例的图，用BFS就是如下这样：

广度优先

• 1.顶点v入队列
• 2.当队列非空时则继续执行，否则算法结束
• 3.出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
• 4.查找顶点v的一个邻接顶点close
• 5.若colse未被访问过的，则colse入队列。
• 6.继续查找顶点v的另一个新的邻接顶点new_col,转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）

package JZ66_Robot_move;
import java.util.*;
/*广度优先
 * 1.顶点v入队列
 * 2.当队列非空时则继续执行，否则算法结束
 * 3.出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
 * 4.查找顶点v的一个邻接顶点close
 * 5.若colse未被访问过的，则colse入队列。
 * 6.继续查找顶点v的另一个新的邻接顶点new_col,转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
 */
 //创建一个类似C++中的Pair结构,用于存放下标x,y
class Pair {
	private int meb_x;
	private int meb_y;
	public Pair(int x,int y) {
		this.meb_x=x;
		this.meb_y=y;
	}
	public int getX() {
		return meb_x;
	}
	public int getY() {
		return meb_y;
	}
}

public class Bfs_Move {
	private final int[] dir={1, 0, -1 , 0, 1};
	//下标转换
	public int check(int n) {
		int sum=0;
		while(n>0) {
			sum+=(n%10);
			n/=10;
		}
		return sum;
	}
	public static void main(String[] args) {
		System.out.print("Enter a row:"); 
    	Scanner sc=new Scanner(System.in);
        int rows=sc.nextInt();
        System.out.println("Enter a columns:");
        int columns=sc.nextInt();
        System.out.println("Enter a threshold:"); 
        int threshold=sc.nextInt();
        int[][] mark=new int[rows][columns];
        for(int i=0;i<rows;i++) {
        	for(int j=0;j<columns;j++) {
        		mark[i][j]=0;
        	}
        }
        int count=0;
        Bfs_Move bfs=new Bfs_Move();
        //创建一个队列,根据它的先进先出的特性,我们可以把顶点v中的所有近邻节点先存入,
        //然后一层一层按照先后顺序添加进队列中,实现广度遍历
        Queue<Pair> q=new LinkedList<Pair>();
        q.add(new Pair(0,0));
        mark[0][0]=1;
        count++;
        //只要队列一直不为空,就不结束循环
        while(!q.isEmpty()) {
        	//poll()会返回队列第一个元素,同时删除这个元素
        	Pair p=q.poll();
            //注意和DFS中的区别,DFS利用此循环进行递归,会一直先按照一个方向,比如此时的右,当访问到最后节点就回溯到之前按照其他方向一次探索
        	//在BFS中则是按照节点周围一圈先添加,在添加外面节点周围一圈
        	for(int i=0;i<4;i++) {
        		int x=p.getX()+bfs.dir[i+1];
        		int y=p.getY()+bfs.dir[i];
        		//可以观察 广度优先的遍历顺序
        		System.out.println("x y:"+x+" "+y);
        		int sum_xy=bfs.check(x)+bfs.check(y);
        		if(x>=0&&x<rows&&y>=0&&y<columns&&sum_xy<=threshold&&mark[x][y]!=1) {
        			count++;
        			mark[x][y]=1;
        			q.add(new Pair(x,y));
        		}
        	}
        }
        System.out.println(count);
	}
}

本文地址：https://blog.csdn.net/weixin_43568893/article/details/107877710