利用加权quick-union来进行判断连连看

2024-01-24 22:48

本文主要是介绍利用加权quick-union来进行判断连连看,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码:

package Algorithm;import java.util.Scanner;public class SeriesLook {
/** 连连看进行判断是否连接* 利用加权quick——union来进行判断是否连接* 存储图的是一个二维数组,首先进行初始* 思路:首先要利用qu中的性质来判断是否是相连的,性质则是每两个点之间要先连,则如果是零就要初始值,在构造函数中已经将其初始值了* 		但是进行判断的时候还需要初始值,就是一个点判断是否与隔壁点相连,则需要判断四个点,才可以确认,则我们可以初始值左边,上边,右边* 		然后再判断三个点进行,即为上点与中心点是否为0,左点,右点也是这样。如果满足,则将其进行比较根节点* 		最后输出yes还是no* */private static int[][] data;private static int[][] id;private int[][] num;private int count;public SeriesLook(int N,int M) {//横竖的值count = N;//记录初始值的分量id = new int[N][M];num = new int[N][M];for(int i =0;i<N;i++) {for(int j=0;j<M;j++) if(data[i][j]==0)//如果是0就可以走{id[i][j]=i*100+j;//赋值为原值num[i][j]=1;}}}public int count() {return count;//返回长度}public boolean connected(int p,int q) {return find(p)==find(q);}public int find(int p) {int i = p/100;//获取横坐标int j = p%100;//获取纵坐标while(id[i][j]!=p) {int temp=id[i][j];//下一个节点i = temp/100;j = temp%100;p = temp;}return p;//为最后的根节点}public void union(int p,int q) {//进行判断是否进行创新新节点int i=find(p);//找寻其节点int j = find(q);if(i==j) return ;if(num[i/100][i%100]<num[j/100][j%100]) {//判断谁的子节点多,多的话则将其设为大树id[i/100][i%100]=j;//头节点指向j的头几点num[j/100][j%100]+=num[i/100][i%100];}else {id[j/100][j%100]=i;num[i/100][i%100]+=num[j/100][j%100];}count--;}public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);System.out.println("输入n.m");int n = scanner.nextInt();//横坐标int m = scanner.nextInt();//纵坐标System.out.println("输入数据:");data = new int[n][m];for(int i =0;i<n;i++)for(int j=0;j<m;j++)data[i][j]=scanner.nextInt();System.out.println("输入要判断的数值:");int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();int d = scanner.nextInt();data[a][b]= 0;data[c][d] = 0;SeriesLook sl = new SeriesLook(n,m);//初始值,必须两个点来进行判才可以判断是否连接,所以需要初始值for(int i =1;i<m;i++) {//初始值横坐标if(data[0][i]==0&&data[0][i-1]==0) {sl.union(i, i-1);//首行两个点则进行判断}}for(int i =1;i<n;i++) {//纵坐标if(data[i][0]==0&&data[i-1][0]==0) {sl.union(i*100, (i-1)*100);}}for(int i=1;i<n;i++)for(int j=1;j<m;j++) {//上左右比较System.out.println("+"+1%100);if(data[i-1][j]==0&&data[i][j]==0)//上比较sl.union((i-1)*100+j, i*100+j);if(data[i][j-1]==0&&data[i][j]==0)//左比较sl.union(i*100+j-1, i*100+j);}for(int i =0;i<n;i++) {for(int j = 0;j<m;j++) {System.out.print(id[i][j]+" ");}System.out.println();}if(sl.connected(a*100+b, c*100+d))System.out.println("yes");elseSystem.out.println("no");}}

这篇关于利用加权quick-union来进行判断连连看的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/641261

相关文章

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

linux解压缩 xxx.jar文件进行内部操作过程

《linux解压缩xxx.jar文件进行内部操作过程》:本文主要介绍linux解压缩xxx.jar文件进行内部操作,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、解压文件二、压缩文件总结一、解压文件1、把 xxx.jar 文件放在服务器上,并进入当前目录#

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用