| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14466 | Counting herds |
|
| 14467 | N-elephants |
|
Description
Elephants are social animals, and for them, adjacent elephants are considered part of the same herd (diagonal adjacency does not count). In other words, if an elephant is located at coordinates (x, y), then the elephants at (x+1, y), (x-1, y), (x, y+1), and (x, y-1) belong to the same herd.
Given a map of size n*m, where # represents an elephant and . represents an empty space, the task is to determine the total number of herds.
Sample:
.#.#.
####.
##..#
....#
##.##
Input
The first line contains two integers, n and m.
1 ≤ n, m ≤ 1000
The following n lines each contain a string of length m, where each character is either # or ..
Output
Output the number of herds.
Note that you do NOT need to print '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We all know that elephants today are mainly divided into two species, the African elephant and the Asian elephant. Therefore, in chess, we also have two different pieces representing them.
The African elephant is larger in size, so its attack range is also bigger. Conversely, the Asian elephant is smaller, so its attack range is smaller.
The Afircan elephants can attack pieces that are in the same row, the same column, or diagonally. In other words, an African elephant can attack pieces on the chessboard just like the queen in chess.
The Asian elephants can attack pieces that are in the same row, the same column, or exactly 2 squares away diagonally (4, 6, 8... squares away diagonally does NOT count). In other words, an elephant located at coordinates (x, y) can attack pieces on the chessboard at (x-2, y-2), (x-2, y+2), (x+2, y-2), (x+2, y+2), (x, *), and (*, y) (where * represents any number).
Given an n * n map with obstacles on some squares (the elephant cannot be placed on them), letter O represents the empty squares and letter X represents the obstacles. Please output the number of ways to place n elephants on the chessboard without attacking each other, the species type of query will represent as k.
If k = 0, the query type is African elephants, else if k = 1, the query type is Asian elephants.
For test cases 1~4, the k = 0.
For test cases 5~6, the k = 1.
Input
The first line contains two integers n and k.
1 ≤ n ≤ 10
k is either 0 or 1.
The following n lines each contain a string of length n, where each character is either letter O or X.
Output
Output the number of ways to place n elephants on the chessboard.
Note that you do NOT need to print '\n' at the end of the output.