本文主要是介绍利用加权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来进行判断连连看的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
