ナイトガードの正方形の数を確認する

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

Iが入力最初の例にw orks、私は入力された第2の例を、それは私に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の位置にある2人の騎士は、両方ともF5で正方形に移動できます。したがって、投稿されたコードはこの位置を2桁とカウントします。理論的には、8つの異なる位置に8人の騎士がいる可能性があり、すべてが同じ広場に移動することができます。これらの可能性のある「重複」ポジションを排除するためのチェックが行われなければなりません。

私は、KnightGuardクラスとgetSafePositionsメソッドで少し混乱しています。 KnightGuardクラスには位置のリストがあり、これは与えられたナイトの位置のリストです。しかし、getSafePositionsメソッドは、すべての騎士がそれぞれの位置から移動できる異なる移動の数を返します。この方法では、前の騎士も最初の段落で説明したのと同じ位置に移動できることを考慮していません。

簡素化する...私はKnightというクラスがより良いアプローチになると感じています。騎士はPositionという変数を持っていて、 "この"騎士がどこに置かれているかを示します。加えて、Knightクラスは、ArrayListのPositionオブジェクトを含み、このナイトがその位置を与えられる可能性のあるすべての動きを示す。 Knightは、他のKnightsを認識してはならず、移動可能な位置のリストは、その位置に別のピースがあるかどうかにかかわらず、移動可能なすべての位置です。このリストには、最低2つのポジションと最大8つの異なるポジションが含まれます。

新しいKnightオブジェクトが作成されると、可能な移動のリストは、インスタンス化時に自動的に生成され、ボード上の独自の位置が自動的に生成されます。

以下はこのKnightクラスの例です。このクラスとメインの方法では、ボードのインデクシングを左から0（ゼロ）で始まり、右に移動するように変更し、yインデックスでも下のyインデックス1で上に上がる。さらに、SetValidMovesメソッドが作成され、このナイトが移動可能な位置のリストを変更できるようになりました。これは、別の騎士がこの騎士の守備位置リストの1つの位置を占める場合に必要となるかもしれません。このコードでは、ガードされた四角形の数にのみ関心があるため、これを利用していません。 ArrayListKnightのオブジェクト（knightsOnBoard）で

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

それがループすることが可能である。このリストを考え、各Position位置騎士の1つ以上がガードされていることを示しArrayListPositionのオブジェクト（validMoves）を作成します。重複は望ましくないので、既にvalidMovesリストにある位置は無視されます。

knightsOnBoardは、上記のコードは、位置がリストvalidMovesに既に存在するかどうかを確認するcontainsプロパティを使用しているので、変化が公に露出するPositionクラスで必要とされる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; 
} 

のグローバルリストであります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; 
} 

は、今、私たちは重複していないArrayListPositionのオブジェクトを持っています。残念ながら、クリアするための最後のハードルが1つあります。 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 PLUS騎士の数。

最後に、以下の主な方法ですべて一緒にこれを置きます。コードでは、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(); 
}