4110262_ac_219ms_4832k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

char map[1001][1001];
int n, m;
int cnt;
int flag;
int bad;
int visited[1001][1001];
int mov[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

bool valid(int x, int y)
{
	return x >= 0 && y >= 0 && x < n && y < m && map[x][y] != '.' && visited[x][y] != flag;
}
int L, R, T, B;

void flood(int a, int b)
{
	cnt++;
	if (a < T)	T = a;
	if (a > B)	B = a;
	if (b < L)	L = b;
	if (b > R)	R = b;
	visited[a][b] = flag;
	for (int i = 0; i < 8; i++)
	{
		int x = a + mov[i][0];
		int y = b + mov[i][1];
		if (valid(x, y))
		{
			flood(x, y);
		}
	}
}

int main()
{
	int ans;
	int i, j;

	flag = 100;
	while (true)
	{
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0)
		{
			break;
		}
		ans = 0;
		bad = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%s", map[i]);
		}
		flag++;
		for (i = 0; !bad && i < n; i++)
		{
			for (j = 0; !bad && j < m; j++)
			{
				if (map[i][j] == '.' || visited[i][j] == flag)
				{
					continue;
				}
				cnt = 0;
				L = T = 100000;
				R = B = -1;
				flood(i, j);
				ans++;
				bad = (cnt != (R - L + 1) * (B - T + 1));
			}
		}
		if (bad)
			puts("Bad placement.");
		else
			printf("There are %d ships.\n", ans);
	}
	return 0;
}