pku2734.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
char st[1001][1001];
typedef struct 
{
	int x, y;
	char n;
} Pos;

Pos p[1000];

const int Kdis[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
const int Qdis[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

int la, lb;

int in(int x, int y)
{
	if (x < 1 || y < 1 || x > la || y > lb)
	{
		return 0;
	}
	return 1;
}

int main()
{
	int i, j, t, x, y, caset = 0, k, tmx, tmy;
	while (scanf("%d%d", &la, &lb) != -1)
	{
		if (la == 0 && lb ==0)
		{
			break;
		}

		for (i = 1; i <= la; i++)
		{
			memset(st[i] + 1, 0, sizeof(st[0][0]) * lb);
		}
		
		i = 0;
		scanf("%d", &t);
		while (t--)
		{
			scanf("%d%d", &x, &y);
			st[x][y] = 'Q';
			p[i].x = x;
			p[i].y = y;
			p[i].n = 'Q';
			i++;
		}
		scanf("%d", &t);
		while (t--)
		{
			scanf("%d%d", &x, &y);
			st[x][y] = 'K';
			p[i].x = x;
			p[i].y = y;
			p[i].n = 'K';
			i++;
		}
		scanf("%d", &t);
		while (t--)
		{
			scanf("%d%d", &x, &y);
			st[x][y] = 'P';
			p[i].x = x;
			p[i].y = y;
			p[i].n = 'P';
			i++;
		}

		while (i-- > 0)
		{
			if (p[i].n == 'P')
			{
				continue;
			}
			if (p[i].n == 'K')
			{
				x = p[i].x;
				y = p[i].y;
				for (j = 0; j < 8; j++)
				{
					tmx = x + Kdis[j][0];
					tmy = y + Kdis[j][1];
					if (in(tmx, tmy) && st[tmx][tmy] == 0)
					{
						st[tmx][tmy] = 1;
					}
				}
			}

			if (p[i].n == 'Q')
			{
				x = p[i].x;
				y = p[i].y;
				for (j = 0; j < 8; j++)
				{
					for (k = 1; ; k++)
					{
						tmx = x + k * Qdis[j][0];
						tmy = y + k * Qdis[j][1];
						if (in(tmx, tmy) == 0)
						{
							break;
						}
						if (st[tmx][tmy] == 0 || st[tmx][tmy] == 1)
						{
							st[tmx][tmy] = 1;
							continue;
						}
						else
						{
							break;
						}
					}
				}
			}
		}

		for (i = 1, k = 0; i <= la; i++)
		{
			for (j = 1; j <= lb; j++)
			{
				if (st[i][j] == 0)
				{
					k++;
				}
			}
		}
		printf("Board %d has %d safe squares.\n", ++caset, k);
	}
	
	return 0;
}