確定騎士衛隊的正方形數

Question

我在爲這項任務生產正確的輸出時遇到了一些麻煩，不知道我在做什麼錯。

N×N棋盤上有K個騎士，你要確定他們守衛多少個方格。如果一個方格被一個 騎士佔領，或者騎士可以通過一次移動到達，則守衛一個方格。 編寫一個程序，讀取騎士的正整數N和K以及騎士的K位置，並打印由這些K騎士守衛的方格數量。輸入的

實施例：8 2 c 1 e 2

通訊輸出：10

輸入的實施例：8 6 c 1 e 2 d 4 c 7 f 7 h 6

通訊輸出：30

當我輸入的第一個例子它w ^獸人，但是當我輸入第二個例子中它給了我34

package knightguard; 

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.Scanner; 
import java.util.Set; 

public class KnightGuard { 

    static class Position { 

     int x; 
     int y; 

     public Position(int x, int y) { 
      this.x = x; 
      this.y = y; 
     } 

     public boolean equals(Position p) { 
      if (p.x == x && p.y == y) { 
       return true; 
      } 
      return false; 
     } 

     @Override 
     public String toString() { 
      return x + "," + y; 
     } 

    } 

    ArrayList<Position> knightPositions; 
    int size; 
    int no_of_knights; 

    public KnightGuard(int size, int k, ArrayList<Position> knightPositions) { 
     this.knightPositions = knightPositions; 
     no_of_knights = k; 
     this.size = size; 
    } 

    public int getSafePositions() { 
     Set<Position> safePos = new HashSet<>(); 
     for (Position p : knightPositions) { 
      if (isValid(p.x - 2, p.y - 1)) { 
       safePos.add(new Position(p.x - 2, p.y - 1)); 
      } 
      if (isValid(p.x - 2, p.y + 1)) { 
       safePos.add(new Position(p.x - 2, p.y + 1)); 
      } 
      if (isValid(p.x + 2, p.y - 1)) { 
       safePos.add(new Position(p.x + 2, p.y - 1)); 
      } 
      if (isValid(p.x + 2, p.y + 1)) { 
       safePos.add(new Position(p.x + 2, p.y + 1)); 
      } 

      if (isValid(p.x - 1, p.y - 2)) { 
       safePos.add(new Position(p.x - 1, p.y - 2)); 
      } 
      if (isValid(p.x - 1, p.y + 2)) { 
       safePos.add(new Position(p.x - 1, p.y + 2)); 
      } 
      if (isValid(p.x + 1, p.y - 2)) { 
       safePos.add(new Position(p.x + 1, p.y - 2)); 
      } 
      if (isValid(p.x + 1, p.y + 2)) { 
       safePos.add(new Position(p.x + 1, p.y + 2)); 
      } 
     } 

     return safePos.size(); 
    } 

    private boolean isValid(int x, int y) { 
     if (x < 0 || x >= size || y < 0 || y >= size) { 
      return false; 
     } 

     if (knightPositions.contains(new Position(x, y))) { 
      return false; 
     } 

     return true; 
    } 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     int size = s.nextInt(); 
     int knights = s.nextInt(); 
     ArrayList<Position> knightPos = new ArrayList<>(); 
     for (int i = 0; i < knights; i++) { 
      int x = s.next().charAt(0) - 'a'; 
      int y = s.nextInt() - 1; 
      knightPos.add(new Position(x, y)); 
     } 

     KnightGuard knightGuard = new KnightGuard(size, knights, knightPos); 
     System.out.println(knightGuard.getSafePositions()); 

     s.close(); 

    } 

} 

Answer 1

一個問題在使用這種方法的缺點是可能重複的位置可以針對不同的騎士產生。例;使用帖子中的圖片，位置D4和H6處的兩名騎士都可以移動到F5處的方塊。因此，發佈的代碼將計算這個位置TWICE。理論上，在八個不同的位置可能有八（8）個騎士，並且都可以移動到同一個方格。必須進行檢查以消除這些可能的「重複」位置。

我有點困惑KnightGuard類和getSafePositions方法。 KnightGuard職業有一個職位列表，這是給定騎士職位的列表。然而，這個方法只是返回所有騎士可以從其各自位置移動的不同移動數量。這種方法沒有考慮到先前的騎士也可以移動到與第一段所述的相同的位置。

爲了簡化事情...我覺得一個名爲Knight的類會是一個更好的方法。騎士將有一個Position變量來指示「THIS」騎士在棋盤上的位置。此外，Knight類將包含一個Position對象，用於指示該騎士在其位置所能做出的所有可能移動。一個Knight不應該知道任何其他Knights，它可以移動到的位置列表是它可以移動到的所有位置，而不管該位置是否有另一塊。該清單將包含至少兩（2）個職位和最多八（8）個不同職位。

當創建一個新的Knight對象時，可能的移動列表將在實例化時自動生成，以及它自己在板上的位置，我們稍後將需要它。

下面是這個Knight類的一個例子。應該注意的是，在這個類和主要方法中，我改變了電路板的索引，從左邊的1（a）開始不爲零（0），並且向右移動，並且還在y索引的底部y索引處是1並向上移動。另外創建一個SetValidMoves方法來允許這個騎士可以移動的位置列表被改變。如果另一名騎士佔據騎士被守衛位置列表中的其中一個位置，則可能需要這樣做。由於我們只對守衛方格的數量感興趣，所以這段代碼並沒有利用這一點。

public class Knight { 

    Position knightPosition; 
    ArrayList<Position> validMoves; 
    int boardSize; 

    public Knight(Position position, int inBoardSize) { 
    knightPosition = position; 
    validMoves = new ArrayList<Position>(); 
    boardSize = inBoardSize; 
    SetValidMoves(); 
    } 

    public Position GetKnightPosition() { 
    return knightPosition; 
    } 

    public ArrayList<Position> GetValidMoves() { 
    return validMoves; 
    } 
    public void SetValidMoves(ArrayList<Position> newMoves) { 
    validMoves = newMoves; 
    } 

    private void SetValidMoves() { 
    int thisX = knightPosition.x; 
    int thisY = knightPosition.y; 
    // check for bottom moves 2 down 1 left - right 
    if (thisY - 2 >= 1) { 
     if (thisX + 1 <= boardSize) { 
     validMoves.add(new Position(thisX + 1, thisY - 2)); 
     } 
     if (thisX - 1 >= 1) { 
     validMoves.add(new Position(thisX - 1, thisY - 2)); 
     } 
    } 
    // check for bottom moves 1 down 2 left - right 
    if (thisY - 1 >= 1) { 
     if (thisX + 2 <= boardSize) { 
     validMoves.add(new Position(thisX + 2, thisY - 1)); 
     } 
     if (thisX - 2 >= 1) { 
     validMoves.add(new Position(thisX - 2, thisY - 1)); 
     } 
    } 
    // check for top moves 2 up 1 left - right 
    if (thisY + 2 <= boardSize) { 
     if (thisX + 1 <= boardSize) { 
     validMoves.add(new Position(thisX + 1, thisY + 2)); 
     } 
     if (thisX - 1 >= 1) { 
     validMoves.add(new Position(thisX - 1, thisY + 2)); 
     } 
    } 
    // check for top moves 1 up 2 left - right 
    if (thisY + 1 <= boardSize) { 
     if (thisX + 2 <= boardSize) { 
     validMoves.add(new Position(thisX + 2, thisY + 1)); 
     } 
     if (thisX - 2 >= 1) { 
     validMoves.add(new Position(thisX - 2, thisY + 1)); 
     } 
    } 
    } 
} 

隨着Knight的ArrayList一個對象（knightsOnBoard）能夠循環認爲該列表，並創建Position對象（validMoves），其中每個Position指示的位置的一個或多個的騎士守着的ArrayList。由於不需要重複，因此我們只是忽略已在validMoves列表中的位置。

knightsOnBoard是Knight全局對象列表

private static ArrayList<Position> GetAllDifferentPositions() { 
    ArrayList<Position> validMoves = new ArrayList<Position>(); 
    for (Knight curKnight : knightsOnBoard) { 
    for (Position curPos : curKnight.validMoves) { 
     if (!validMoves.contains(curPos)) { 
     validMoves.add(curPos); 
     } 
    } 
    } 
    return validMoves; 
} 

由於上述代碼使用contains屬性來檢查，如果位置是已經在列表中validMoves，需要在Position類的改變公開揭露使用Object參數的equals方法。

@Override 
public boolean equals(Object obj) { 
    if (obj instanceof Position) { 
    Position other = (Position)obj; 
    if (this.x == other.x && this.y == other.y) 
     return true; 
    } 
    return false; 
} 

現在我們有沒有重複的Position的ArrayList對象。不幸的是，還有最後一道難題要清除。需要檢查一下Knight是否可以移動到正方形，但它已經被另一個騎士佔領了。因此，我們需要移除騎士可以移動到的位置列表中的所有「騎士」位置。

這個必須要做的原因是我們需要把所有給定的Knight的位置加到計數上，因爲騎士所在的方格也是一個「守護」的方格。由於這個位置可能已經在列表中......我們需要刪除它們。換句話說，我們知道一個Knight在其移動列表中不會有「自己的」位置，但它在其移動列表中可能會有另一個Knight的位置。

private static void RemoveAllKnightPositions(ArrayList<Position> allPositions) { 
    for (Knight curKnight : knightsOnBoard) { 
    if (allPositions.contains(curKnight.knightPosition)) { 
     allPositions.remove(curKnight.knightPosition); 
    } 
    } 
} 

現在位置（finalResults下）的列表中有沒有重複，另外，我們知道列表中不包含任何其中一個騎士坐着的位置。因此，守護方的數量將是位置列表中finalResults加上騎士的數量。

最後，把這一切放在下面的主要方法。請注意，代碼更改索引順序，所以x和y從1開始並在boardSize結束。我希望這是有道理的，並有幫助。

static ArrayList<Knight> knightsOnBoard = new ArrayList<Knight>(); 

public static void main(String[] args) { 
    Scanner s = new Scanner(System.in); 
    int boardSize = s.nextInt(); 
    int knights = s.nextInt(); 
    for (int i = 0; i < knights; i++) { 
     int x = (s.next().charAt(0) - 'a') + 1; 
     int y = s.nextInt(); 
     Knight newKnight = new Knight(new Position(x,y), boardSize); 
     knightsOnBoard.add(newKnight); 
     System.out.println("Knight at : " + newKnight.knightPosition.x + " " + newKnight.knightPosition.y); 
    } 

    ArrayList<Position> finalResults = GetAllDifferentPositions(); 
    RemoveAllKnightPositions(finalResults); 
    System.out.println("Positions: " + (finalResults.size() + knightsOnBoard.size())); 
    s.close(); 
}