# Kattis - nineknights

[題目連結](https://open.kattis.com/problems/nineknights)

## 題目敘述

In the game of chess, knights are unique due to their “L-shaped” movement. A knight can move, as shown in Figure $1$, by either moving two squares sideways and one square up or down, or moving one square sideways and two squares either up or down.


Figure 1: The highlighted squares show all possible moves for a knight.

In the Nine Knights puzzle, exactly nine knights must be positioned on a 5-by-5 board so that no knight can attack another knight with a single move. The configuration shown in Figure 2 is an invalid solution because two of the knights can attack each other, where the configuration shown in Figure 3 is a valid solution.


Figure 2: Invalid game configuration


Figure 3: Valid game configuration

Given the description of a game configuration, your job is to determine whether or not it represents a valid solution to the Nine Knights puzzle.

:::success
在西洋棋中，騎士因 $L$ 型的走法而顯得十分獨特。
騎士的移動方式如圖 $1$ 所示，水平移動 $2$ 格遠且上下移動 $1$ 格遠，
或者水平移動 $1$ 格遠且上下移動 $2$ 格遠。

圖 $1$：綠色為騎士能移動的範圍。

在《九騎士》的益智遊戲中，玩家必須在 $5\times 5$ 的棋盤，擺上剛好 $9$ 隻騎士，
使得這些騎士只花一步無法攻擊到其它騎士。
圖 $2$ 示範了一種不合法的擺放方式，並標出了會互相攻擊的兩隻騎士，
圖 $3$ 則示範了一種合法的擺放方式。

圖 $2$：不合法的擺放方式。

圖 $3$：合法的擺放方式。

給你一個遊戲中的盤面，你必須判斷該盤面是否為一種合法的擺放方式。
:::

## 輸入格式

The input will consist of $5$ lines, each having $5$ characters. All characters will be either `’k’`, indicating the placement of a knight, or `’.’`, indicating an empty space on the board.

:::success
輸入包含 $5$ 行，每行剛好 $5$ 個字元。
每個字元可能是代表騎士的 `k` 或代表空格的 `.` 這兩種。
:::

## 輸出格式

Display the word `valid` if the given chess board is a valid solution to the Nine Knights puzzle. Otherwise, display the word `invalid`.

:::success
如果給定盤面為《九騎士》的合法盤面，輸出 `valid`；
如果不是，輸出 `invalid`。
:::

## Sample Input

...k.
...k.
k.k..
.k.k.
k.k.k

## Sample Output

invalid

## Sample Input

.....
...k.
k.k.k
.k.k.
k.k.k

## Sample Output

valid

## Sample Input

.....
...k.
k.k.k
.k.k.
k...k

## Sample Output

invalid

{%hackmd @sa072686/__style %}

###### tags: `翻譯`, `Kattis`