import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

class Stars {
public static void main(String[] args) throws NumberFormatException, IOException {
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {

String[] dimensions = br.readLine().split(" ");
int x = Integer.parseInt(dimensions[0]), y = Integer.parseInt(dimensions[1]);

char[][] sky = new char[x][y];
for(int i = 0; i < x; i++)
sky[i] = br.readLine().toCharArray();

int stars = 0;

for(int i = 0; i < x; i++)
for(int j = 0; j < y; j++)
if (sky[i][j] == '*') stars++;

if (x == 1 && y == 1)
; // do nothing

else if (x == 1 && y != 1) {
for(int j = 1; j < y; j++)
if (sky[0][j] == '*' && sky[0][j] == sky[0][j - 1]) stars--;
}

else if (x != 1 && y == 1) {
for(int i = 1; i < x; i++)
if (sky[i][0] == '*' && sky[i][0] == sky[i - 1][0]) stars--;
}

else {
boolean visited[][] = new boolean[x][y];
for(int i = 0; i < x; i++)
for(int j = 0; j < y; j++)
if (sky[i][j] == '*') stars = count(visited, sky, i, j, stars, x, y);
}
out.println(stars);
}
out.flush();
}

public static int count(boolean[][] visited, char[][] sky, int i, int j, int stars, int x, int y) {
visited[i][j] = true;
if (i == 0 && j == 0) {
if (sky[0][1] == '*' && !visited[0][1]) {
stars--;
stars = count(visited, sky, 0, 1, stars, x, y);
}
if (sky[1][1] == '*' && !visited[1][1]) {
stars--;
stars = count(visited, sky, 1, 1, stars, x, y);
}
if (sky[1][0] == '*' && !visited[1][0]) {
stars--;
stars = count(visited, sky, 1, 0, stars, x, y);
}
}
else if (i == x - 1 && j == 0) {
if (sky[i - 1][0] == '*' && !visited[i - 1][0]) {
stars--;
stars = count(visited, sky, i - 1, 0, stars, x, y);
}
if (sky[i - 1][1] == '*' && !visited[i - 1][1]) {
stars--;
stars = count(visited, sky, i - 1, 1, stars, x, y);
}
if (sky[i][1] == '*' && !visited[i][1]) {
stars--;
stars = count(visited, sky, i, 1, stars, x, y);
}
}
else if (i == 0 && j == y - 1) {
if (sky[0][j - 1] == '*' && !visited[0][j - 1]) {
stars--;
stars = count(visited, sky, 0, j - 1, stars, x, y);
}
if (sky[1][j - 1] == '*' && !visited[1][j - 1]) {
stars--;
stars = count(visited, sky, 1, j - 1, stars, x, y);
}
if (sky[1][j] == '*' && !visited[1][j]) {
stars--;
stars = count(visited, sky, 1, j, stars, x, y);
}
}
else if (i == x - 1 && j == y - 1) {
if (sky[i][j - 1] == '*' && !visited[i][j - 1]) {
stars--;
stars = count(visited, sky, i, j - 1, stars, x, y);
}
if (sky[i - 1][j - 1] == '*' && !visited[i - 1][j - 1]) {
stars--;
stars = count(visited, sky, i - 1, j - 1, stars, x, y);
}
if (sky[i - 1][j] == '*' && !visited[i - 1][j]) {
stars--;
stars = count(visited, sky, i - 1, j, stars, x, y);
}
}
else if (i == 0 && j > 0 && j < y - 1) {
if (sky[0][j - 1] == '*' && !visited[0][j - 1]) {
stars--;
stars = count(visited, sky, 0, j - 1, stars, x, y);
}
if (sky[0][j + 1] == '*' && !visited[0][j + 1]) {
stars--;
stars = count(visited, sky, 0, j + 1, stars, x, y);
}
if (sky[1][j - 1] == '*' && !visited[1][j - 1]) {
stars--;
stars = count(visited, sky, 1, j - 1, stars, x, y);
}
if (sky[1][j] == '*' && !visited[1][j]) {
stars--;
stars = count(visited, sky, 1, j, stars, x, y);
}
if (sky[1][j + 1] == '*' && !visited[1][j + 1]) {
stars--;
stars = count(visited, sky, 1, j + 1, stars, x, y);
}
}
else if (i > 0 && i < x - 1 && j == 0) {
if (sky[i - 1][0] == '*' && !visited[i - 1][0]) {
stars--;
stars = count(visited, sky, i - 1, 0, stars, x, y);
}
if (sky[i + 1][0] == '*' && !visited[i + 1][0]) {
stars--;
stars = count(visited, sky, i + 1, 0, stars, x, y);
}
if (sky[i - 1][1] == '*' && !visited[i - 1][1]) {
stars--;
stars = count(visited, sky, i - 1, 1, stars, x, y);
}
if (sky[i][1] == '*' && !visited[i][1]) {
stars--;
stars = count(visited, sky, i, 1, stars, x, y);
}
if (sky[i + 1][1] == '*' && !visited[i + 1][1]) {
stars--;
stars = count(visited, sky, i + 1, 1, stars, x, y);
}
}
else if (i == x - 1 && j > 0 && j < y - 1) {
if (sky[i][j - 1] == '*' && !visited[i][j - 1]) {
stars--;
stars = count(visited, sky, i, j - 1, stars, x, y);
}
if (sky[i][j + 1] == '*' && !visited[i][j + 1]) {
stars--;
stars = count(visited, sky, i, j + 1, stars, x, y);
}
if (sky[i - 1][j - 1] == '*' && !visited[i - 1][j - 1]) {
stars--;
stars = count(visited, sky, i - 1, j - 1, stars, x, y);
}
if (sky[i - 1][j] == '*' && !visited[i - 1][j]) {
stars--;
stars = count(visited, sky, i - 1, j, stars, x, y);
}
if (sky[i - 1][j + 1] == '*' && !visited[i - 1][j + 1]) {
stars--;
stars = count(visited, sky, i - 1, j + 1, stars, x, y);
}
}
else if (i > 0 && i < x - 1 && j == y - 1) {
if (sky[i - 1][j] == '*' && !visited[i - 1][j]) {
stars--;
stars = count(visited, sky, i - 1, j, stars, x, y);
}
if (sky[i + 1][j] == '*' && !visited[i + 1][j]) {
stars--;
stars = count(visited, sky, i + 1, j, stars, x, y);
}
if (sky[i - 1][j - 1] == '*' && !visited[i - 1][j - 1]) {
stars--;
stars = count(visited, sky, i - 1, j - 1, stars, x, y);
}
if (sky[i][j - 1] == '*' && !visited[i][j - 1]) {
stars--;
stars = count(visited, sky, i, j - 1, stars, x, y);
}
if (sky[i + 1][j - 1] == '*' && !visited[i + 1][j - 1]) {
stars--;
stars = count(visited, sky, i + 1, j - 1, stars, x, y);
}
}
else if (i > 0 && i < x - 1 && j > 0 && j < y - 1) {
if (sky[i - 1][j] == '*' && !visited[i - 1][j]) {
stars--;
stars = count(visited, sky, i - 1, j, stars, x, y);
}
if (sky[i + 1][j] == '*' && !visited[i + 1][j]) {
stars--;
stars = count(visited, sky, i + 1, j, stars, x, y);
}
if (sky[i - 1][j - 1] == '*' && !visited[i - 1][j - 1]) {
stars--;
stars = count(visited, sky, i - 1, j - 1, stars, x, y);
}
if (sky[i + 1][j + 1] == '*' && !visited[i + 1][j + 1]) {
stars--;
stars = count(visited, sky, i + 1, j + 1, stars, x, y);
}
if (sky[i - 1][j + 1] == '*' && !visited[i - 1][j + 1]) {
stars--;
stars = count(visited, sky, i - 1, j + 1, stars, x, y);
}
if (sky[i + 1][j - 1] == '*' && !visited[i + 1][j - 1]) {
stars--;
stars = count(visited, sky, i + 1, j - 1, stars, x, y);
}
if (sky[i][j - 1] == '*' && !visited[i][j - 1]) {
stars--;
stars = count(visited, sky, i, j - 1, stars, x, y);
}
if (sky[i][j + 1] == '*' && !visited[i][j + 1]) {
stars--;
stars = count(visited, sky, i, j + 1, stars, x, y);
}
}
return stars;
}

public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

Wyszukiwarka

Podobne podstrony:
gwiazdki na bloga(7)
gwiazdki na bloga(2)
Hydrologia na niebiesko
gwiazdki na bloga
De Mono Statki Na Niebie
Statki na Niebie
STATKI NA NIEBIE
Perseidy urządzą spektakl na niebie
karp na niebiesko
De Mono Statki na niebie
Statki na niebie txt

więcej podobnych podstron