2336.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2336 on 2006-08-26 at 12:37:35 */ 
#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
using namespace std;

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

char map[N][N];
int w, h, n, rd[N], rh, cw;

void erase(int, int);

int main()
{
	for(int t = 1; true; t++) {
		for(h = 0; true; h++)
			if(gets(map[h]) == NULL) return 0;
			else if(!islower(map[h][0])) break;
		w = strlen(map[0]);
		for(int i = 0; i < h; i++) rd[i] = w;
		sscanf(map[h], "%d", &n); rh = 0; cw = w;
		for(int i = 0; i < n; i++) {
			int a, b; scanf("%d %d\n", &a, &b);
			erase(rh+a-1, b-1);
		}
		printf("Test case #%d:\n", t);
		for(int i = rh; i < h; i++, putchar('\n'))
			for(int j = 0; j < cw; j++)
				putchar(map[i][j]);
	}
}

void erase(int a, int b)
{
	queue<int> Q; Q.push((a<<10)|b);
	char e = map[a][b]; map[a][b] = ' ';
	int dx = a, ly = b;
	while(!Q.empty()) {
		int p = Q.front(), x = p>>10, y = p&1023; Q.pop();
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(cx >= h || cx < rh || cy < 0 || cy >= rd[cx] || map[cx][cy] != e) continue;
			map[cx][cy] = ' '; Q.push((cx<<10)|cy);
			dx >?= cx; ly <?= cy;
		}
	}
	cw = 0;
	for(int i = rh; i <= dx; i++) {
		int od = rd[i], nd = ly;
		for(int j = ly; j < od; j++)
			if(map[i][j] != ' ') { char t = map[i][j]; map[i][j] = ' '; map[i][nd++] = t; }
		rd[i] = nd;
	}
	for(int i = rh; i < h; i++) cw >?= rd[i];
	for(int i = cw-1; i >= ly; i--)
		for(int j = dx, tw = dx+1; j >= rh; j--)
			if(map[j][i] != ' ') {
				char t = map[j][i]; map[j][i] = ' '; map[--tw][i] = t;
				if(map[j][i+1] == ' ') rd[j] <?= i;
				rd[tw] >?= i+1;
			}
	while(h != rh && rd[rh] == 0) rh++;
}