Peking Online Judge – 1009 – Edge Detection

Warning! Spoiler ahead!


#include "stdafx.h"
#include <iostream>
#include <fstream>

using namespace std;

ofstream myFile;

int edgeLength;
int totalEdge;

int prevEncPixel = -1;
int encPixelCount = 0;

int img[1001][4];

int width = 0;

int rowCount = 0;

void restart(){
	edgeLength = -1;
	totalEdge = -1;
	
	prevEncPixel = -1;
	encPixelCount = 0;
		
	width = 0;
	
	rowCount = 0;

	for(int i=0;i<1001;i++){
		img[i][0] = 0;
		img[i][1] = 0;
		img[i][2] = 0;
		img[i][3] = 0;
	}
}

int* getPixelGroup(int pos){
	int count = 0;
	while(pos > img[count][3]) count++;
	return img[count];
}

int getMaxValue(int globalPos, int currValue){

	int positions[8] = {globalPos - width - 1, globalPos - width, globalPos - width + 1, globalPos - 1, globalPos + 1, globalPos + width - 1, globalPos + width, globalPos + width + 1};
	
	int max = 0;
	
	bool left = globalPos % width == 0;
	bool right = globalPos % width == width - 1;
	bool up = globalPos / width == 0;
	bool down = globalPos / width == rowCount - 1;

	for(int i= 0; i < 8; i++){
		if(left && (i == 0 || i == 3 || i == 5)  || 
		   right && (i == 2 || i == 4 || i == 7) ||
		   up && (i < 3) ||
		   down && (i > 4)) continue;
		
		int value = getPixelGroup(positions[i])[0];

		int absDif = abs(value - currValue);

		if(absDif > max)
			max = absDif;
	}

	return max;
}

bool isTopBorder(int pos){
	return pos < -1;
}

bool isBottomBorder(int pos){
	return pos/width >= rowCount;
}

const int getStripLength(int pos, int* pixelGroup, bool border){
	int ret = border ? width : min(pixelGroup[3] - pos + 1, width - pos % width);
	if(pos % width == 0 || border) ret ++;
	if((pos % width) + pixelGroup[1] - (pos - pixelGroup[2]) >= width || border) ret++;
	return ret;
}

void checkPixels(int pixelValue, int count){
	if(pixelValue == prevEncPixel)
		{
			encPixelCount += count;
		}
		else
		{
			if(prevEncPixel != -1){
				myFile << prevEncPixel << " " << encPixelCount<<endl;
			}
			prevEncPixel = pixelValue;
			encPixelCount = count;
		}
}


void encode(int groupCount, int groupIndex, int width){
	int* group = img[groupIndex];
	int qty = group[1];
	int currGlobalPos = group[2];

	bool twoEdges = qty > totalEdge;

	int topLeft, topStripLength, topPixels; 
	int centerPixel, leftPixel, rightPixel, middlePixels, currentPos, stripLength;
	int bottomLeft, bottomStripLength, bottomPixels;
	bool topBorder, leftBorder, bottomBorder, rightBorder;

	int totalRows = (currGlobalPos % width + qty) / width;

	if((currGlobalPos % width + qty) % width != 0) totalRows ++;
	int i = 0;
	while(i < qty){	
		
		currentPos = currGlobalPos + i;
		leftBorder = currentPos % width == 0;
		
#pragma region TopStrip
		topLeft =  currentPos - width - 1;
		topBorder = isTopBorder(topLeft);
		int* topPixelGroup = topBorder ? group : getPixelGroup(topLeft + (leftBorder?1:0));
		
		topPixels = topPixelGroup[0];

		topStripLength = getStripLength(topLeft + (leftBorder?1:0),topPixelGroup, topBorder);
#pragma endregion

#pragma region BottomStrip
		bottomLeft =  currentPos + width - 1;
		bottomBorder = isBottomBorder(bottomLeft + (leftBorder?1:0));
		int* bottomPixelGroup = bottomBorder ? group : getPixelGroup(bottomLeft + (leftBorder?1:0));
		
		bottomPixels = bottomPixelGroup[0];
		
		bottomStripLength = getStripLength(bottomLeft + (leftBorder?1:0), bottomPixelGroup, bottomBorder);
#pragma endregion

		stripLength = min(max(topStripLength - 2,1), min(max(bottomStripLength - 2,1), min(qty - (currentPos - group[2]), width)));
		leftPixel =  getMaxValue(currentPos, group[0]);
		
		checkPixels(leftPixel, 1);

		if(stripLength >= 2){
			if(stripLength > 2)
			{
				centerPixel = getMaxValue(currentPos + 1, group[0]);
				checkPixels(centerPixel,stripLength - 2);
			}
			rightPixel = getMaxValue(currentPos + stripLength-1, group[0]);
			checkPixels(rightPixel,1);
		}

		i += stripLength;

		if(twoEdges && i < edgeLength){
			int topEdgeRows = currGlobalPos % width != 0 ? 2 : 1;
			int bottomEdgeRows = group[3] % width != width-1 ? 2 : 1;
			
			int zeroCount = width * (totalRows - topEdgeRows - bottomEdgeRows);
			checkPixels(0,zeroCount);
			i += zeroCount;

		}
	}
}

int main()
{	
	myFile.open("example2.txt");

	cin >> width;

	while(width != 0){
		myFile << width << endl;
		
		edgeLength = width + 1;
		totalEdge = edgeLength * 2;

		int pixel, qty = -1;


		int count= 0;
		
		int totalPixels = 0;

		while(qty != 0){
			cin >> pixel >> qty;

			img[count][0] = pixel;
			img[count][1] = qty;
			img[count][2] = count == 0 ? 0 : img[count-1][2] + img[count-1][1];
			img[count][3] = img[count][2]+qty-1;		

			totalPixels += qty;

			count++;
		}

		rowCount = totalPixels / width;

		int i = 0;

		while(img[i][1] != 0){

			encode(count - 1, i++, width);

		}
		myFile << prevEncPixel << " " << encPixelCount<<endl;
		myFile << 0<< " " << 0<<endl;
		count = 0;

		restart();

		cin >> width;
	}
	myFile << 0;
	myFile.close();
	return 0;
}

1 comment

Leave a Reply

Your email address will not be published. Required fields are marked *