pku2920.cpp

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

#include <stdio.h>
#include <string.h>
#define SIZE 310

typedef struct Qnode
{
	int x, y;
}Qnode;

Qnode Q[SIZE * SIZE];
int F[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
int N;
char map[SIZE][SIZE];
bool vis[SIZE][SIZE];
int In(int x, int y){return x > 0 && y > 0 && x <= N && y <= N;}

void init(int t)
{
	int i, M, j, x, y, nx, ny;
	scanf("%d", &N);
	memset(map, '?', sizeof(map));
	memset(vis, false, sizeof(vis));
	scanf("%d", &M);
	while (M--)
	{
		scanf("%d %d", &x, &y);
		map[x][y] = '*';
		for (i = 0; i < 8; i++)
		{
			nx = x + F[i][0];
			ny = y + F[i][1];
			if (map[nx][ny] != '*')
				map[nx][ny] = '#';
		}
	}
	printf("Scenario #%d:\n",t);
}

void solve()
{
	int i, j, x, y, nx, ny;
	int head, tail;
	x = y = (N + 1) / 2;
	Q[0].x = x;
	Q[0].y = y;
	vis[x][y] = true;
	head = 0;
	tail = 1;
	if (map[x][y] == '?')
	while (head < tail)
	{
		x = Q[head].x;
		y = Q[head].y;
		head++;
		for (i = 0; i < 8; i++)
		{
			nx = x + F[i][0];
			ny = y + F[i][1];
			if (!In(nx, ny) || vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			if (map[nx][ny] == '#')
				continue;
			Q[tail].x = nx;
			Q[tail].y = ny;
			tail++;
		}
	}
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			if (map[i][j] == '*')
				printf("*");
			else if (map[i][j] == '#' && vis[i][j] == true)
				printf("#");
			else if (map[i][j] == '?' && vis[i][j] == true)
				printf(".");
			else
				printf("?");
		}
		printf("\n");
	}
	printf("\n");
}

int main()
{
	int t, T;
	scanf("%d", &T);
	for (t = 1; t <= T; t++)
	{
		init(t);
		solve();
	}
}