Start: Dec, 04, 2016 12:00:00
杭州师范大学第十届程序设计竞赛—正式
End: Dec, 04, 2016 17:00:00
Time elapsed:
Time remaining:

Problem_ID: J
Result: Accepted
Time: 2ms
Memory: 1356kB
In contest: 1075

#include <stdio.h>
#include <stdlib.h>

int n, m, z;
int a[101][101] = {{0}};
int use[101][101] = {{0}};

void dfs(int x, int y);

int main()
{
	int i, j, k, l, ans = 0;
	char ch;
	scanf("%d %d%*c", &n, &m);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			scanf("%c", &ch);
			if (ch == '*')
			{
				a[i][j] = 1;
			}
			else
			{
				if (ch == '.')
				{
					a[i][j] = 0;
				}
			}
		}
		scanf("%*c");
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && ! use[i][j])
			{
				use[i][j] = 1;
				z = 1;
				dfs(i, j);
				ans += z;
			}
		}
	}
	printf("%d", ans);
}

void dfs(int x, int y)
{
	if (x == 0 || x == n - 1 || y == 0 || y == m - 1)
	{
		z = 0;
	}
	if (x > 0 && a[x - 1][y] == 0 && use[x - 1][y] == 0)
	{
		use[x - 1][y] = 1;
		dfs(x - 1, y);
	}
	if (x < n - 1 && a[x + 1][y] == 0 && use[x + 1][y] == 0)
	{
		use[x + 1][y] = 1;
		dfs(x + 1, y);
	}
	if (y > 0 && a[x][y - 1] == 0 && use[x][y - 1] == 0)
	{
		use[x][y - 1] = 1;
		dfs(x, y - 1);
	}
	if (y < m - 1 && a[x][y + 1] == 0 && use[x][y + 1] == 0)
	{
		use[x][y + 1] = 1;
		dfs(x, y + 1);
	}
}