linux创建文件 soap nhibernate constructor sdk swiftui Draggabilly 品优购电商系统开发 linux内存管理 rxjava线程切换 ubuntu更改文件夹权限 mysql函数返回结果集 idea开发python python开发工具 java语言介绍 hadoop权威指南 win10长期服务版 微信小程序提示框 python队列 dota改键工具 cms教程 big5 生存猎人属性 7个人 js包含字符串 大势至usb监控 hyqihei sqlprompt 刻刀工具 易语言tv 人脸识别代码 劳动节称号 pr怎么加字幕特效 origin柱状图 ps涂抹工具快捷键 pr如何抠图 idt声卡补丁 blockingqueue 怎么退出小米账号 python链表
当前位置: 首页 > 学习教程  > 编程语言

Acwing---1100. 抓住那头牛 (Java)_BFS模板

2021/2/13 19:08:41 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

1100. 抓住那头牛 ①. 题目②. 思路③. 学习点④. 代码实现原题链接 ①. 题目 ②. 思路 每次移动共有三种状态,我们可以使用BFS层次搜索,三种状态的操作值都是1,又是求得最少操作时间,也就是最少操作次数,当BFS层次按…

1100. 抓住那头牛

  • ①. 题目
  • ②. 思路
  • ③. 学习点
  • ④. 代码实现

原题链接

①. 题目

在这里插入图片描述

②. 思路

  • 每次移动共有三种状态,我们可以使用BFS层次搜索,三种状态的操作值都是1,又是求得最少操作时间,也就是最少操作次数,当BFS层次按三种操作层次搜索,当优先搜索到目标值,直接返回dist[k]的最短距离,BFS搜索每次都是优先最短距离进行搜索

③. 学习点

一维数组进行BFS

④. 代码实现

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class _1100_抓牛_一维数组BFS求最短路径 {
	static int N=100010;
	static int n;
	static int k;
	static int[] dist=new int[N];  //dist[k]表示k点到n点的最短距离
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();
		 k = sc.nextInt();
		 System.out.println(bfs());
	}
	static int bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(n);
		Arrays.fill(dist, -1);
		dist[n]=0;
		while(!queue.isEmpty()) {
			int t = queue.poll();
			if(t==k) {
				return dist[k];
			}
			//操作A
			if(t-1>=0&&dist[t-1]==-1) {
				dist[t-1]=dist[t]+1;
				queue.offer(t-1);
			}
			//操作B
			if(t+1<N&&dist[t+1]==-1) {
				dist[t+1]=dist[t]+1;
				queue.offer(t+1);
			}
			//操作C
			if(2*t<N&&dist[2*t]==-1) {
				dist[2*t]=dist[t]+1;
				queue.offer(2*t);
			}
		}
		return -1;
	}
}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700277.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?