117 lines
2.7 KiB
Python
117 lines
2.7 KiB
Python
"""
|
|
Backtracking Framework
|
|
- Set of choices
|
|
- Limited by constraints
|
|
- To reach a goal
|
|
|
|
1. Understand
|
|
- Board of W/B, can capture; looking for max consecutive sequence of captures using same piece
|
|
- Capture in any direction "skipping over"; land on open square
|
|
|
|
Similar Problems: N Queens
|
|
|
|
Set of candidates (W pieces) limited in moves (capturing B pieces) to reach max # captures (i.e. capturing moves)
|
|
2. Develop
|
|
|
|
- Given board state, w/ W candidates
|
|
- Consider every candidate as the piece yielding correct answer
|
|
- For every candidate, consider every capturing move they can make
|
|
- For each move:
|
|
- Make the move, and recursively find max # captures using this piece after this capture
|
|
- update/restore state on failure
|
|
- Update max if new max found
|
|
|
|
consider after: caching/optimization
|
|
|
|
backtracking function: def max_captures(board, w) -> int:
|
|
|
|
|
|
3. Carry Out
|
|
4. Revise
|
|
|
|
At any particular position,
|
|
"""
|
|
|
|
BOARD_SIZE = 10
|
|
|
|
|
|
def parse_board() -> tuple[list[list[str]], list[tuple[int, int]]]:
|
|
board = []
|
|
candidates: list[tuple[int, int]] = []
|
|
|
|
input()
|
|
|
|
for r in range(BOARD_SIZE):
|
|
board.append(list(input()))
|
|
|
|
candidates.extend((r, c) for c, cell in enumerate(board[-1]) if cell == "W")
|
|
|
|
return board, candidates
|
|
|
|
|
|
def valid(board, r, c):
|
|
return 0 <= r < len(board) and 0 <= c < len(board[0])
|
|
|
|
|
|
# all capturing moves white piece can make
|
|
def capturing_moves(board, r, c) -> list[tuple[int, int]]:
|
|
if not valid(board, r, c):
|
|
return []
|
|
|
|
moves = []
|
|
|
|
for dr, dc in [(-1, -1), (1, 1), (-1, 1), (1, -1)]:
|
|
if (
|
|
valid(board, r + 2 * dr, c + 2 * dc)
|
|
and board[r + dr][c + dc] == "B"
|
|
and board[r + 2 * dr][c + 2 * dc] not in "BW"
|
|
):
|
|
moves.append((dr, dc))
|
|
|
|
return moves
|
|
|
|
|
|
def max_candidate_captures(board, r, c) -> int:
|
|
max_captures = 0
|
|
|
|
for dr, dc in capturing_moves(board, r, c):
|
|
# place
|
|
board[r][c] = "."
|
|
board[r + dr][c + dc] = "."
|
|
board[r + dr * 2][c + dc * 2] = "W"
|
|
|
|
ans = max_candidate_captures(board, r + dr * 2, c + dc * 2)
|
|
max_captures = max(max_captures, 1 + ans)
|
|
|
|
# unplace
|
|
board[r + dr * 2][c + dc * 2] = "."
|
|
board[r][c] = "W"
|
|
board[r + dr][c + dc] = "B"
|
|
|
|
return max_captures
|
|
|
|
|
|
def max_captures(board, candidates: list[tuple[int, int]]) -> int:
|
|
max_captures = 0
|
|
|
|
for r, c in candidates:
|
|
max_captures = max(max_captures, max_candidate_captures(board, r, c))
|
|
|
|
return max_captures
|
|
|
|
|
|
def solve() -> None:
|
|
T = int(input())
|
|
|
|
while T:
|
|
board, candidates = parse_board()
|
|
print(max_captures(board, candidates))
|
|
T -= 1
|
|
|
|
|
|
def main() -> None:
|
|
solve()
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|