Description
Only the template and the parts in red are different from HW
Lizard Tom now has lots and lots of popcorn!
He recently learned how to play Shogi (Japanese chess), a board game where you can resurrect captured pieces and use them as your own. In his free time, he plays against Cabi in the dorm lounge (btw, this is real, you can come play with us). Dominating the board with the Ureshino-Ryū, he aspires to become the Ryuo of NTHU—one of the highest titles in the Shogi world.
One morning, a question suddenly popped into Lizard Tom's mind: On a 5x5 Shogi board, assuming no pieces can attack each other, how many possible board configurations are there if we want to Exactly H_limit of additionally Hisya (飛車, abbreviated as H) pieces , K_limit of additionally Kakugyo (角行, abbreviated as K) pieces, and R_limit of additionally Ryuo (竜王, abbreviated as R) pieces?
No, not again...
To stop Lizard Tom from practicing counting all over again, you decide to write a program to help him calculate the answer !
Pieces attack ranges
- Hisya (H): Attacks all cells in the same row and column
- Kakugyo (K): Attacks all cells along its diagonals
- Ryuo (R): Attacks all cells in the same row and column, plus the four immediately adjacent diagonal cells.
Template Code
# Feel free to modify or rewrite anything you want !
graph = [0] * 29
board = ["."] * 29
dire = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
ans = 0
def put_H (posx: int, posy: int, status: int) -> bool:
pos = 5*(posx-1) + posy
if (status == 1):
if (graph[pos] > 0 or board[pos] != '.'):
return False
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
if (i != posy and board[row] != '.'):
return False
if (i != posx and board[column] != '.'):
return False
board[pos] = 'H'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] += 1
graph[column] += 1
graph[pos] -= 1
return True
else:
board[pos] = '.'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] -= 1
graph[column] -= 1
graph[pos] += 1
return True
def put_K (posx: int, posy: int, status: int) -> bool:
pos = 67 # Yeah this line is obviously wrong
if (status == 1):
# Do Something ...
return True
else:
# Do Something ...
return True
def put_R (posx: int, posy: int, status: int) -> bool:
pos = 5*(posx-1) + posy
if (status == 1):
if (graph[pos] > 0 or board[pos] != '.'):
return False
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
if (i != posy and board[row] != '.'):
return False
if (i != posx and board[column] != '.'):
return False
for (dx, dy) in dire:
nx = posx + dx
ny = posy + dy
if (nx > 0 and ny > 0 and nx < 6 and ny < 6):
diag = 5*(nx-1) + ny
if (board[diag] != '.'):
return False
board[pos] = 'R'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] += 1
graph[column] += 1
graph[pos] -= 1
for (dx, dy) in dire:
nx = posx + dx
ny = posy + dy
if (nx > 0 and ny > 0 and nx < 6 and ny < 6):
diag = 5*(nx-1) + ny
graph[diag] += 1
return True
else:
board[pos] = '.'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] -= 1
graph[column] -= 1
graph[pos] += 1
for (dx, dy) in dire:
nx = posx + dx
ny = posy + dy
if (nx > 0 and ny > 0 and nx < 6 and ny < 6):
diag = 5*(nx-1) + ny
graph[diag] -= 1
return True
def find (start: int, H: int, K: int, R: int) -> None:
# To use global variables ans, H_limit, K_limit, and R_limit in this function,
# the declaration below is required
global ans, H_limit, K_limit, R_limit
# Do something ...
H_limit, K_limit, R_limit = map(int, input().split())
tmp = input()
valid = True
for i in range(1, 26, 1):
x = (i-1)//5 + 1
y = (i-1)%5 + 1
if (tmp[i-1] == 'H'):
if (not put_H(x, y, 1)):
valid = False
elif (tmp[i-1] == 'K'):
if (not put_K(x, y, 1)):
valid = False
elif (tmp[i-1] == 'R'):
if (not put_R(x, y, 1)):
valid = False
if (valid):
find(1, 0, 0, 0)
print(ans)
Here is a quick breakdown of the provided template:
graph: A 1D array representing the 5x5 board. It tracks the attack coverage by counting how many pieces are currently attacking each cell. A value of0means the cell is safe.board: A 1D array representing the 5x5 board state. It tracks the piece currently occupying each cell ('H','K','R', or'.'for empty cells)put_H,put_K,put_R: Helper functions to update thegrapharray. Focusing atposx-rowandposy-column, pass1to thestatusargument when placing a piece (to mark its attack range), and-1when picking it up (to unmark its attack rangek). And of course,boardarray will also be updated in these functionsfind: The core backtracking function you need to complete. The parameters are:start: The 1D cell index (1 to 25) to start scanning from, ensuring you only move forward to avoid duplicate permutations leading to TLEH,K,R: Counters tracking the number of newly placed Hisya, Kakugyo, and Ryuo pieces in the current recursive path.
HINT
- You cannot remove the pieces originally on the board.
- No two pieces can attack each other, whether they are newly placed or originally on the board.
- The total number of newly placed pieces must be exactly N.
- If there are no valid configurations, do not output anything.
- The order of your answer will not affect the result
- Indeed, there's other solutions for this problem (e.g. use lists to record the pieces in every row, column, main diagonal, secondary diagonal, and 3x3 square.) You can try them if you want :)
Input
The input consists of two lines.
The first line consists three positive integer H_limit, K_limit, R_limit, representing the number of pieces to be additionally placed. (To be more precise, the newly placed pieces must satisfy H = H_limit, K = K_limit and R = R_limit. The pieces originally on the board do not count.)
The second line contains a string S of length 25, which may consist of ., H, K, and R. S_i represents the state of the cell with index i: . means an empty cell, while H, K, and R represent Hisya, Kakugyo, and Ryuo, respectively.
We define the index of the cell at row x and column y (0-indexed) as 5x + y.
- The initial board is legal
- For testcase.1 ~ testcase.6, guarantee that
- For testcase.9 ~ testcase.10, the initial board is empty
Output
Output an integer, representing the number of all possible board configurations.