Start 2024-01-20 16:34:09

six--20230121模拟算法

End 2024-02-10 00:00:00
Contest is over.
Now 2025-08-15 13:33:39

F. 计算机病毒

Description

假设有n×n台计算机组成了一个n×n的矩阵,初始时有的计算机感染了病毒,以后每隔一小时会使其邻近的未装杀毒软件的计算机染上病毒,试计算在m小时后感染病毒的计算机数。

Input

第一行为一个整数n(n≤100),表示n×n的矩阵。 接下来n行,每行n个字符,其中‘*’表示初始时未感染病毒的计算机,‘#’表示该计算机已装杀毒软件,‘@’表示初始时已感染病毒的计算机。 最后一行是一个整数m(m≤100),表示小时数。

Output

一个整数,即第m小时后感染病毒的计算机数。

Examples

Input

5
****#
*#*@*
*#@**
#****
*****
4

Output

19

Hint

注:书中输出样例为16,实际应为19,请以网站的19为准


Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit