UVA 00183 Bit Maps Binary search simulation

p00183.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200

char grid[MAXN][MAXN];
void clean(){
	char c;
	while ((c = getchar()) != '\n' && c != EOF);
}

void inputB(int r, int c){
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j){
			// cout << "Input grid ";
			grid[i][j] = getchar();
			// cout << grid[i][j];
		}
	clean();
}

void print(int r, int c){
	// cout << "Inside print \n";
	for (int i = 0; i < r; ++i){
		for (int j = 0; j < c; ++j)
			putchar(grid[i][j]);
	}
		puts("");
}

string sol;
void changeB(int left, int right, int top, int bottom){
	if (left > right || top > bottom) return;
	bool split = false;
	for (int r = top; r <= bottom; ++r)
		for (int c = left; c <= right; ++c)
			if (grid[r][c] != grid[top][left]) {
				split = true; break;
			}

	if (split){
		sol.push_back('D');
		int rowMid = (top + bottom) / 2;
		int colMid = (left + right) / 2;
		changeB(left, colMid, top, rowMid);			//top left quarter
		changeB(colMid + 1, right, top, rowMid);	//top right quarter
		changeB(left, colMid, rowMid + 1, bottom);	//bottom left
		changeB(colMid + 1, right, rowMid + 1, bottom);	//bottom right
	}
	else sol.push_back(grid[top][left]);
}

list<char> l;
void changeD(int left, int right, int top, int bottom){
	if (left > right || top > bottom) return;
	char cur = l.front(); 
	l.pop_front();
	if (cur == 'D'){
		//split
		int rowMid = (top + bottom) / 2;
		int colMid = (left + right) / 2;
		changeD(left, colMid, top, rowMid);			//top left quarter
		changeD(colMid + 1, right, top, rowMid);	//top right quarter
		changeD(left, colMid, rowMid + 1, bottom);	//bottom left
		changeD(colMid + 1, right, rowMid + 1, bottom);	//bottom right
	}
	else 
		for (int r = top; r <= bottom; ++r)
			for (int c = left; c <= right; ++c)
				grid[r][c] = cur;
}

int main(){
	char type;
	int r, c;
	while ((type = getchar()) != '#'){
		scanf("%d %d", &r, &c);
		clean();
		printf("%c %4d%4d\n", type, r, c);
		if (type == 'B') { 
			inputB(r, c);
			changeB(0,c-1,0,r-1);
			puts(sol.c_str());
			sol.clear();
		}
		else if (type == 'D'){
			char x;
			while(x = getchar())
				if (isalnum(x)) l.push_back(x);
				else {
					if (x != '\n') clean();
					break;
				}
				changeD(0, c-1, 0, r-1);
				print(r, c);
		}
		// print(r, c);
	}
	return 0;
}