1749.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1749 on 2005-12-10 at 01:05:06 */ 
#include <cstdio>
#include <cstring>

const int MAX = 64;

class Step {
public:
	int x, y;
};

int w, l;

void set(int, int, bool[MAX][MAX], bool);

int main()
{
	int n, t;
	int i, j, k, case_no;
	Step step[MAX][MAX];
	bool hide[MAX][MAX];

	for(case_no = 1; scanf("%d %d %d %d", &w, &l, &n, &t) != EOF && 
		w != 0 && l != 0 && n != 0 && t != 0; case_no++) {
		memset(hide, true, sizeof(hide));
		for(i = 0; i < n; i++) {
			for(j = 0; j < t; j++) {
				scanf("%d %d", &step[i][j].x, &step[i][j].y);
			}
		}
		for(i = 0; i < n; i++) {
			set(step[i][0].y, step[i][0].x, hide, false);
		}
		for(i = 1; i < t; i++) {
			for(j = 0; j < n; j++) {
				set(step[j][i].y, step[j][i].x, hide, false);
			}
			bool next[MAX][MAX] = { false };
			for(j = 0; j <= l; j++) {
				for(k = 0; k <= w; k++) {
					if(hide[j][k]) {
						set(j, k, next, true);
					}
				}
			}
			for(j = 0; j < n; j++) {
				set(step[j][i].y, step[j][i].x, next, false);
			}
			for(j = 0; j <= l; j++) {
				for(k = 0; k <= w; k++) {
					hide[j][k] = next[j][k];
				}
			}
		}
		int print = 0;
		printf("Observation Set %d\n", case_no);
		for(i = 0; i <= l; i++) {
			for(j = 0; j <= w; j++) {
				if(hide[i][j]) {
					if(print % 8 == 0) {
						if(print != 0) {
							putchar('\n');
						}
					} else {
						putchar(' ');
					}
					printf("(%d,%d)", j, i);
					print++;
				}
			}
		}
		if(print == 0) {
			printf("No possible locations");
		}
		putchar('\n');
	}
	
	return 0;
}

void set(int x, int y, bool map[MAX][MAX], bool v)
{
	map[x][y] = v;
	if(x > 0)  map[x-1][y] = v;
	if(x < l)  map[x+1][y] = v;
	if(y > 0)  map[x][y-1] = v;
	if(y < w)  map[x][y+1] = v;
}