pku1856.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 192 行

#include <stdio.h>

char ship[1001][1001];
int st[1001][1001];
int idst[5000][2];
int N, M;
int dis[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

int in(int i, int j)
{
	if (i >= 0 && i < N && j >= 0 && j < M)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void cls(int x, int y, int id)
{
	int i, nextx, nexty;
	st[x][y] = id;
	for (i = 0; i < 8; i++)
	{
		nextx = x + dis[i][0];
		nexty = y + dis[i][1];
		
		if (in(nextx, nexty) && st[nextx][nexty] == -1)
		{
			cls(nextx, nexty, id);
		}
	}
}

int test(int p)
{
	int sx, sy, ex, ey;
	int i, j;
	sx = idst[p][0];
	sy = idst[p][1];
	ex = sx + 1;
	while (ex < N && st[ex][sy] == p) ex++;
	ex--;
	ey = sy + 1;
	while (ey < M && st[sx][ey] == p) ey++;
	ey--;

	for (i = sx + 1; i <= ex; i++)
	{
		for (j = sy + 1; j <= ey; j++)
		{
			if (st[i][j] != p)
			{
				return 0;
			}
		}
	}

	if (in(sx - 1, sy))
	{
		for (i = sy; i <= sy; i++)
		{
			if (st[sx - 1][i] == p)
			{
				return 0;
			}
		}
	}

	if (in(ex + 1, sy))
	{
		for (i = sy; i <= ey; i++)
		{
			if (st[ex + 1][i] == p)
			{
				return 0;
			}
		}
	}

	if (in(sx, ey + 1))
	{
		for (i = sx; i <= ex; i++)
		{
			if (st[i][ey + 1] == p)
			{
				return 0;
			}
		}
	}

	if (in(sx, sy - 1))
	{
		for (i = sx; i <= ex; i++)
		{
			if (st[i][sy - 1] == p)
			{
				return 0;
			}
		}
	}

	if (in(sx - 1, sy - 1) && st[sx - 1][sy - 1] == p)
	{
		return 0;
	}

	if (in(sx - 1, ey + 1) && st[sx - 1][ey + 1] == p)
	{
		return 0;
	}

	if (in(ex + 1, sy - 1) && st[ex + 1][sy - 1] == p)
	{
		return 0;
	}

	if (in(ex + 1, ey + 1) && st[ex + 1][ey + 1] == p)
	{
		return 0;
	}
	return 1;
}

int main()
{
	int i, j, count = 0, id;
	while (scanf("%d%d", &N, &M) != -1)
	{
		if (N == 0 && M == 0)
		{
			break;
		}

		for (i = 0; i < N; i++)
		{
			scanf("%s", ship[i]);
		}

		for (i = 0; i < N; i++)
		{
			for (j = 0; j < M; j++)
			{
				
				if (ship[i][j] == '.')
				{
					st[i][j] = -2;
				}
				else
				{
					st[i][j] = -1;
				}
			}
		}

		for (i = 0, id = 0; i < N; i++)
		{
			for (j = 0; j < M; j++)
			{
				if (st[i][j] == -1)
				{
					cls(i, j, id);
					idst[id][0] = i;
					idst[id][1] = j;
					id++;
				}
			}
		}
		
		for (i = 0, count = 0; i < id; i++)
		{
			if (test(i))
			{
				count++;
			}
		}
		if (count == id)
		{
			printf("There are %d ships.\n", count);
		}
		else
		{
			printf("Bad placement.\n");
		}
	}
	return 0;
}