加權快速聯盟

我目前正在做拼貼算法，並且我們被要求使用加權快速聯盟製作十六進制遊戲，演講者給出了項目的大部分代碼。但是我遇到了一個問題here.`public類六角實現棋盤遊戲{加權快速聯盟

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"); 

    } 

}

來源

2013-10-02 user2175076

哪裏n1和n2從何而來？ – Markus

請詳細解釋哪些方法對您的解決方案無效。目前我只看到很多代碼和建議，並不是所有的東西都可以按照你的意願工作。 –

例如，當我把board [1] [1] = player 1，我必須在WeightedQuickUnionUF類中找到那個位置和它的鄰居，現在如果我做了wqu.find（board [1] [1]），這是等於1，因此它找到id [1]是1。現在，如果我搜索neighours，他們也將等於1，這隻會鏈接回id [1]。然後我可以檢查一下，如果沒有通過wqu.union（board [1] [1]，board [2] [3]）連接它們，他們是否是聯盟），但它似乎連接了板上的每個點，所以如果我檢查wqu.connected（board [1] [1]，board [3] [3]）它將返回true。希望這有助於解釋它或讓你更加困惑 – user2175076

您有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' 
}

來源

2014-01-01 18:44:08

加權快速聯盟

回答

相關問題