Description

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 additionally place N pieces consisting of Hisya (飛車, abbreviated as H), Kakugyo (角行, abbreviated as K), and Ryuo (竜王, abbreviated as R)?

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

You're strongly suggested to understand what the template code is doing and how it works before you start. As a heartbroken lizard, Tom may not give you the complete template on Lab：（

# Feel free to modify or rewrite anything you want

graph = [0] * 29
board = ["."] * 29
dire = [(1, 1), (-1, -1), (1, -1), (-1, 1)]

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 = 5*(posx-1) + posy
    if (status == 1):
        if (graph[pos] > 0 or board[pos] != '.'):
            return False
        for (dx, dy) in dire:
            tmpx = posx + dx
            tmpy = posy + dy
            while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
                diag = 5*(tmpx-1) + tmpy
                if (board[diag] != '.'):
                    return False
                tmpx += dx
                tmpy += dy

        board[pos] = 'K'
        graph[pos] += 1
        for (dx, dy) in dire:
            tmpx = posx + dx
            tmpy = posy + dy
            while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
                diag = 5 * (tmpx - 1) + tmpy
                graph[diag] += 1
                tmpx += dx
                tmpy += dy
        return True
    else:
        board[pos] = '.'
        graph[pos] -= 1
        for (dx, dy) in dire:
            tmpx = posx + dx
            tmpy = posy + dy
            while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
                diag = 5*(tmpx-1) + tmpy
                graph[diag] -= 1
                tmpx += dx
                tmpy += dy
        return True

def put_R (posx: int, posy: int, status: int) -> bool:
    pos = 5*(posx-1) + posy
    if (status == 1):
        # Do something ...
        return True
    else:
        # Do something...
        return True

def find (start: int, H: int, K: int, R: int, N: int) -> None:
    if (H+K+R >= N):
        # Do something ...
    # Do something ...

# ===============================================

N = int(input())
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, N)

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.
  • N: The target total number of pieces to be additionally placed.

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 is a positive integer N, representing the number of pieces to be additionally placed. (To be more precise, the newly placed pieces must satisfy H + K + R = N. 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.

Output

Output all possible board configurations. For each valid configuration, output a string of length 25 followed by a newline. The formatting rules are the same as the INPUT.

Sample Input  Download

Sample Output  Download

Discuss

Description

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 count how many different groups of friends are inviting him out.

---

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 total number of friend groups -- 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.

Output

Print a single integer — the total number of friend groups.

Sample Input  Download

Sample Output  Download

Discuss