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 of 0 means 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 the graph array. Focusing at posx-row and posy-column, pass 1 to the status argument when placing a piece (to mark its attack range), and -1 when picking it up (to unmark its attack rangek). And of course, board array will also be updated in these functions
• find: 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 TLE
  • H, 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.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Only the parts in red are different from HW

---

Lizard Tom is tired of his boring life. He really wants to go out and play with his friends!

Cabi says he will take a group to the Coffee Club to drink lots of coffee and stay up all night. That sounds super fun! Money says he will drive everyone to get midnight snacks. Even though Tom just ate 75 buckets of popcorn, who can say no to food? A RedCapeFlyingCat wants to study together for homework, because a mean TA made a problem about "Ryuo or something", and he has been stuck on it for two hours already.

Huh... Down time certain!

Only poor CS students do their I2P homework—Tom is a happy lizard !

Anyway, too many friends are inviting Tom. Tom cannot even tell if friend A and friend B are actually planning the same party! So, he wants you to write a program to help him decide which group to join.

Tom likes to be with a bunch of friends, as many as possible! Therefore, he will join the group with the most members without any doubt.

---

Tom has friends, numbered from to . You are given plans. Each plan has two numbers and , meaning friend and friend will hang out together, so they are in the same group.

If anyone in group hangs out with anyone in group , group and group will merge into one single group (in other words, each group is a connected component). Any friend who has no plans with anyone is simply in their own group of size 1.

Print one integer: the number of members in the group that has the most members -- You'd better finish quickly while Tom is still doing his wiggle dance, or he will start guessing the answer from 1 once again !

Input

The first line contains two integers and — the number of friends and the number of plans.

The next lines each contain two integers and , meaning friend and friend are hanging out together.

It is guaranteed that there are no self-loops () and no duplicate plans.

• For testcase.1 ~ testcase.6, guatantee that

Output

Print one integer: the number of members in the group that has the most members

Sample Input  Download

Sample Output  Download

Tags

Discuss