2308.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2308 on 2006-08-07 at 14:00:00 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 320;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, 
						{ 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

int n, mine[N][N];
char map[N][N];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
void dfs(int, int);

int main()
{
	int t, T, i, j, m;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		memset(map, '?', sizeof(map)); memset(mine, 0, sizeof(mine));
		for(i = 0; i < n; i++) map[i][n] = 0;
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			map[a-1][b-1] = '*';
			for(j = 0; j < 8; j++) {
				int x = a-1+DIR[j][0], y = b-1+DIR[j][1];
				if(legal(x, y)) mine[x][y]++;
			}
		}
		dfs(n>>1, n>>1);
		printf("Scenario #%d:\n", t+1);
		for(i = 0; i < n; i++) puts(map[i]);
		putchar('\n');
	}
	
	
	return 0;
}

void dfs(int x, int y)
{
	if(map[x][y] != '?') return;
	map[x][y] = mine[x][y] ? '#' : '.';
	if(mine[x][y]) return;
	int i;
	for(i = 0; i < 8; i++) {
		int nx = x+DIR[i][0], ny = y+DIR[i][1];
		if(legal(nx, ny)) dfs(nx, ny);
	}
}