867 . Star Battle Puzzle

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

M_SQRT

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

100.0% (6/6)

Tags

ntucpc-speedrun1

Description

你有玩過 Star Battle Puzzle 嗎？Star Battle Puzzle 是一個解謎遊戲，每一道謎題都會以一個空的 $9\times 9$ 盤面開始，該盤面會被切割成若干個區塊。玩家的目的是在一些空格填入一些「星星」，滿足：

  • 每一行都有恰兩個星星
  • 每一列都有恰兩個星星
  • 每一個區塊都有恰兩個星星
  • 任兩個星星都不得八方位相鄰

下圖是一道空的盤面及其解答的示意圖：

現在，請你撰寫一支程式，在讀入一個已經填好星星的 Star Battle Puzzle 盤面後，輸出該盤面是否有被完整解決。意即填入的星星是否有滿足所有指定條件。

Input Format

輸入首先會是空盤面的資訊，共有九行，每行九個字元，每個字元皆為數字 $\texttt{1}$ 至 $\texttt{9}$ 其中之一，代表該格隸屬於的區塊編號。

緊接著是填入星星的方式，共有九行，每行九個字元，每個字元 . 或 *，其中 . 代表未填入任何東西、* 代表填入一顆星星。

  • 保證給定的空盤面由字元 $\texttt{1}$ 至 $\texttt{9}$ 組成
  • 保證給定的空盤面的共有九個區塊，且每個區塊四方位連通
  • 保證給定的填入星星方式由字元 . 和 * 組成

Output Format

若輸入的填入星星方式滿足所有條件，輸出 $\texttt{Valid}$；否則只要違反任何一個條件，輸出 $\texttt{Invalid}$。

Sample Input 1

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*...*...
...*...*.
.*...*...
...*....*
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 1

Valid

Sample Input 2

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*...*...
...*...*.
.*......*
...*.*...
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 2

Invalid

Sample Input 3

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*.......
...*...*.
.*...*...
...*....*
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 3

Invalid

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~27 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
Submit
Back to Top