Weighted Quick Union

Question

В настоящее время я выполняю Алгоритмы в коллаже, и нас просят сделать шестнадцатеричную игру с использованием взвешенного быстрого объединения, нам дали большую часть кода для проекта лектором. Но им работает в классе проблема here.`public Hex реализует BoardGame {

private int[][] board; // 2D Board. 0 - empty, 1 - Player 1, 2 - Player 2 

private int n1, n2; // height and width of board 

private WeightedQuickUnionUF wqu; // Union Find data structure to keep track 
            // of unions and calculate winner 

private int currentPlayer; // Current player in the game, initialised to 1 

public Hex(int n1, int n2) // create N-by-N grid, with all sites blocked 
{ 
    this.n1 = n1; 
    this.n2 = n2; 
    currentPlayer = 1; 

    // TODO: Create instance of board 
    // TODO: Create instance WeightedQuickUnionUF class 
    wqu = new WeightedQuickUnionUF(14); 
    board = new int[n1][n2]; 

    for(int i=0; i < n1 ; i++){ 
     for(int j = 0; j < n2; j++){ 
      board[i][j] = 0; 

     } 
    } 
} 

/* 
* (non-Javadoc) 
* 
* @see BoardGame#takeTurn(int, int) 
*/ 
@Override 
public void takeTurn(int x, int y) { 

    if(((x > n1) || (x < 0)) || ((y > n2) || (y < 0))) 
    { 
     StdOut.println("Wrong"); 
    } 
    else{ 

     if(board[x][y] == 0){ 
      board[x][y] = currentPlayer; 
     } 
     else{ 
      StdOut.println("Taken"); 
     } 

    } 


    // TODO: check coords are valid 
    // TODO: check if location is free and set to player's value(1 or 2). 

    // TODO: calculate location and neighbours location in 
    // WeightedQuickUnionUF data structure 

    // TODO: create unions to neighbour sites in WeightedQuickUnionUF that 
    // also contain current players value 

    // TODO: if no winner get the next player 

} 



/* 
* (non-Javadoc) 
* 
* @see BoardGame#getCurrentPlayer() 
*/ 
@Override 
public int getCurrentPlayer() { 
    return currentPlayer; 
} 

public void setCurrentPlayer(int currentPlayer) { 
    this.currentPlayer = currentPlayer; 
} 

/* 
* (non-Javadoc) 
* 
* @see BoardGame#getBoard() 
*/ 
@Override 
public int[][] getBoard() { 
    return board; 
} 

private void nextPlayer() { 
    if (currentPlayer == 1) 
     currentPlayer = 2; 
    else 
     currentPlayer = 1; 
} 

/* 
* (non-Javadoc) 
* 
* @see BoardGame#isWinner() 
*/ 
@Override 
public boolean isWinner() { 

    // TODO:check if there is a connection between either side of the board. 
    // You can do this by using the 'virtual site' approach in the 
    // percolation test. 
    return false; 
} 

/** 
* THIS IS OPTIONAL: 
* Modify the main method if you wish to suit your implementation. 
* This is just an example of a test implementation. 
* For example you may want to display the board after each turn. 
* @param args 
* 
*/ 
public static void main(String[] args) { 

    BoardGame hexGame = new Hex(4, 4); 

    while (!hexGame.isWinner()) { 
     System.out.println("It's player " + hexGame.getCurrentPlayer() 
       + "'s turn"); 
     System.out.println("Enter x and y location:"); 
     int x = StdIn.readInt(); 
     int y = StdIn.readInt(); 

     hexGame.takeTurn(x, y); 

    } 

    System.out.println("It's over. Player " + hexGame.getCurrentPlayer() 
      + " wins!"); 

} 

} `

Я уже проверил, если координаты являются действительными и, если место на борту бесплатно. Но я могу показаться, что хочу найти местоположение и соседние места, используя WeightedQuickUnionUF. Любая помощь была бы замечательной, поскольку я пробовал все, что знал до сих пор. Вот класс WeightedQuickUnionUF.

public class WeightedQuickUnionUF { 

    private int[] id; 
    private int[] sz; 
    private int count; 


public WeightedQuickUnionUF(int N){ 
    count = N; 
    id = new int[N]; 
    sz = new int[N]; 
    for(int i = 0 ; i < N; i++){ 
     id[i] = i; 
     sz[i] = i; 
     } 
} 


public int count(){ 
    return count; 
} 

public int find(int p){ 
    while(p != id[p]) 
     p = id[p]; 
    return p; 
} 

public boolean connected(int p, int q){ 
    return find(p) == find(q); 
} 

public void union(int p, int q){ 
    int i = find(p); 
    int j = find(q); 
    if(i == j) return; 

    if(sz[i] < sz[j]){id[i] = j; sz[j] += sz[i];} 
    else    {id[j] = i; sz[i] += sz[j];} 
    count--; 
} 

public static void main(String[] args) { 
    int N = StdIn.readInt(); 
    WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N); 


    while(!StdIn.isEmpty()){ 
     int p = StdIn.readInt(); 
     int q = StdIn.readInt(); 
     if(uf.connected(p,q)) continue; 
     uf.union(p, q); 
     StdOut.println(p + " " + q); 
    } 

    StdOut.println(uf.count() + "components"); 

    } 

} 

Answer 1

У Вас есть ошибка в коде инициализации для SZ []

Оно должно быть:

for(int i = 0 ; i < N; i++){ 
    id[i] = i; 
    sz[i] = 1; // changed to 1 so it indicates the number of nodes for this 'root' 
}