2995516_ac_31ms_3992k.c

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

#include <stdio.h>
#include <string.h>

int mark[1001][1001];
struct pos
{
	int x, y;
}kn[101], qu[101];

int n, m;
int us;

int valid(int x,int y)
{
	if(x<=0||y<=0||x>n||y>m)
		return 0;
	return 1;
}

int nonstop(int x,int y)
{
	if(!valid(x,y)||mark[x][y]==-1)
		return 0;
	return 1;
}

void solve(int i)
{
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
	int j, x, y;
	int dx, dy;
	int tx, ty;

	x = qu[i].x;y = qu[i].y;
	for(j = 0; j < 8; j++)
	{
		tx = x;ty = y;
		dx = mov[j][0];
		dy = mov[j][1];
		tx += dx;ty += dy;
		while(nonstop(tx,ty))
		{
			if(mark[tx][ty]==0)
			{
				us++;
				mark[tx][ty] = 1;
			}
			tx += dx;
			ty += dy;
		}
	}
}

void calc(int i)
{
	int x, y, j;
	int mov[][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};

	x = kn[i].x;y = kn[i].y;
	for(j = 0; j < 8; j++)
	{
		if(valid(x+mov[j][0],y+mov[j][1]))
		{
			if(mark[x+mov[j][0]][y+mov[j][1]]==0)
			{
				us++;
				mark[x+mov[j][0]][y+mov[j][1]] = 1;
			}
		}
	}
}

int main()
{
	int i, k, s, q;
	int x, y, cas = 0;
	
	while(1)
	{
		cas++;
		scanf("%d%d",&n,&m);
		if(n==0&&m==0)
			break;
		us = 0;
		memset(mark,0,sizeof(mark));
		scanf("%d",&q);
		for(i = 0; i < q; i++)
		{
			scanf("%d%d",&qu[i].x,&qu[i].y);
			mark[qu[i].x][qu[i].y] = -1;
		}
		scanf("%d",&k);
		for(i = 0; i < k; i++)
		{
			scanf("%d%d",&kn[i].x,&kn[i].y);
			mark[kn[i].x][kn[i].y] = -1;
		}
		scanf("%d",&s);
		for(i = 0; i < s; i++)
		{
			scanf("%d%d",&x,&y);
			mark[x][y] = -1;
		}
		us = s+q+k;
		for(i = 0; i < q; i++)
		{
			solve(i);
		}
		for(i = 0; i < k; i++)
		{
			calc(i);
		}
		printf("Board %d has %d safe squares.\n",cas,n*m-us);
	}
	return 0;
}