1008

From BluWiki

Задача 1008 условие

Возможное решение

Для кодирования/дикодирования используюется следующий алгоритм: берутся 2 стека, 1-й хранит позиции которые надо посетить на данном шаге. Когда заходим в ячейку проверяем всех соседей и заносим нужных во второй стек. Когда 1-й стек становится пустым, меняем его местами со вторым.

Тесты

CODE

#include <iostream>
#include <list>
#include <string>

using namespace std;

class TPoint
{
public:
	int x,y;
	TPoint(int x0, int y0) { x = x0; y = y0; }
};

int sign(int x) { return x > 0 ? 1:-1; }

void DecodeImage(int N )
{
	short int image[100][100];
	for(int i = 0; i < N; i++)
	{
	 for(int j = 0; j < N; j++)
	 {
		image[i][j] = 0;
	 }
	}

	list<TPoint> currentFront, newFront;
	TPoint Begin(0,0);
	for(int i = 0 ; i < N; i++ )
	{
		int kx, ky;
		cin >> kx >> ky;
		if( i == 0 ) 
		{
			Begin.x = kx;
			Begin.y = ky;
			currentFront.push_back( Begin );
		}
		image[kx][ky] = 1;
	}
	image[Begin.x][Begin.y] = 0;
	cout << Begin.x << " " << Begin.y << endl;
	string DIRECTION = "RTLB";
	while(currentFront.size() > 0)
	{
		while (currentFront.size() > 0 )
		{
			TPoint currPoint = currentFront.front();
			currentFront.pop_front();
			for(int i = 1; i <= 4; i++)
			{
				int dx = sign(2-i)*(i % 2);
				int dy = sign(3-i)*((i+1) % 2);
				int ix = currPoint.x + dx;
				int iy = currPoint.y + dy;
				if( ( ix >= 0 && ix < 11 ) && ( iy >= 0 && iy < 11 ) )
				{
					if(image[ix][iy] == 1)
					{
						newFront.push_back(TPoint(ix, iy));
						image[ix][iy] = 0;
						cout << DIRECTION[i-1];
					}
				}
			}
			if(currentFront.size() > 0) cout << "," << endl;
		}
		if(newFront.size() > 0 ) cout << "," << endl;
		else					 cout << "." << endl;	
		currentFront = newFront;
		newFront.clear();
	}
}

void EncodeImage(TPoint Begin)
{
	short int image[100][100];
	for(int i = 0; i < 10; i++)
	{
	 for(int j = 0; j < 10; j++)
	 {
		image[i][j] = 0;
	 }
	}

  char direction;
	string DIRECTION = "RTLB";
	cin >> direction;
	list<TPoint> currentFront, newFront;
	currentFront.push_back(Begin);
	image[Begin.x][Begin.y] = 1;
	TPoint currPoint(0,0);
	int Count = 1;
	do
	{
		for(list<TPoint>::iterator i = currentFront.begin(); i != currentFront.end(); i++)
		{
			do
			{
				currPoint = *i;
				int index = (int) DIRECTION.find(direction)+1;
				if(index > 0)
				{
					int dx = sign(2-index)*(index % 2);
					int dy = sign(3-index)*((index+1) % 2);
    			int ix = currPoint.x + dx;
					int iy = currPoint.y + dy;
					newFront.push_back(TPoint(ix,iy));
					image[ix][iy] = 1;
					Count++;
				}
				cin >> direction;
			}while( (direction != '.') && (direction != ',' ));
		}
		currentFront.clear();
		currentFront = newFront;
		newFront.clear();
	}while(direction != '.' );

	cout << Count << endl;
	for(int i = 0; i < 10 ; i++)
	{
		for(int j = 0; j < 10 ; j++ )
		{
		  if(image[i][j] == 1) cout << i << " " << j << endl;
		}
	}
}

int main()
{
	char str[10];
	cin.getline(str,5);
	char * space = strstr(str, " ");
	if(space == NULL)
	{
    DecodeImage(atoi(str));
	}
	else
	{
		TPoint Begin(0,0);
		Begin.x = atoi( strtok(str," "));
		Begin.y = atoi( strtok(NULL," "));
		EncodeImage(Begin);
	}

	cin >> str;
	return 0;
}