1575 . 棋盤上的硬幣

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

在 N*M 個格子的棋盤上，每一格可能是空的、也可能恰有一枚硬幣。每一次我們可以對棋盤作以下的操作：


  • 首先從上、下、左、右四個方向裡頭挑一個方向出來。

  • 接著將棋盤上的所有硬幣同時往該方向前進一格。如果移動後某些硬幣超出了棋盤的範圍，則這些硬幣就永遠消失在黑暗之中。


請問至少要進行幾次這樣的操作，使得操作完成後，恰好有 K 枚硬幣留在棋盤上？

Input Format

輸入的第一行有一個整數 T (1<=T<=150) 表示有幾組測資。


每組測試資料的第一行有三個整數 N, M, K (1<=N, M<=30; 0<=K<=N*M)。接下來的 N 行每一行有一個長度為 M 的字串，表示當前棋盤的狀況。我們以 'X' 表示硬幣，以 '.' 表示空格。

Output Format

對於每組測試資料，如果做不到請輸出 -1，否則輸出滿足條件之最少操作次數。

Sample Input 1

3
3 3 3
...
.X.
XXX
3 3 3
...
XX.
XX.
3 4 3
....
.XX.
XXX.

Sample Output 1

1
-1
2

Hints

Problem Source

Migrated from old NTUJ.

topcoder

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 200
Submit
Back to Top