1 Востаннє редагувалося Betterthanyou (21.07.2014 18:47:55)

Тема: Заповнити двовимірний масив зигзагом по діагоналі

На олімпіаді із програмування було таке завдання:
Потрібно написати програму, яка заповнює масив розмірності nxn по заданому правилу:

/*    1  3  4 10 11
      2  5  9 12 19
      6  8 13 18 20
      7 14 17 21 24
     15 16 22 23 25  */

Тобто, заповнення масиву має бути по діагоналі, зверху-вниз, зліва-направо. Причому заповнення ще і зигзагоподібно.
Розмір вводиться із клавіатури х на у і ці числа можуть бути будь якими (1 х 2,1 х 1,19 х 16 і т.д) але не можуть бути менше нуля або не цілочислиними, якщо вводяться такі числа на консоль має вийти повідомлення про помилку. А також файл із результатом має записатися в любий диск.
Хто готується до олімпіади думаю вам буде цікаве це завдання, а хто хоче побачити як я зробив його (на VS13) ->
https://yadi.sk/i/l3KXfhewX3inr

2

Re: Заповнити двовимірний масив зигзагом по діагоналі

Код ліпше публікувати безпосередньо у пості, використовуючи тег code (і spoiler у разі великих блоків коду) :).

I belong to the Dead Generation.
Подякували: Betterthanyou1

3

Re: Заповнити двовимірний масив зигзагом по діагоналі

Прихований текст

#include <iostream>
#include <fstream>
#include <conio.h>
#include <iomanip>
#define  getch(); _getch();
using namespace std;

int number = 1;

struct myclass
{
    int index = 1;
    int *mas_number;
    void cout_String(int y)
    {
        ofstream file("F:\\file.txt",ios::app);
        for (int i = 1; i <= y; i++)
        {
            cout << setw(4) << mas_number[i];
            file << setw(4) << mas_number[i];    
        }
        cout << endl;
        file << "\n";
        file.close();
    }
    void String()
    {
        mas_number[index++] = number;
        number += 1;
    }
    void initialization(int y)
    {
        mas_number = new int[y];
    }
};

void part1(myclass *obekt, int y, int x)
{
    int c = 2,
        i = 1,
        k;
    if (x >= y)
    {
        k = y;
        if (y % 2 == 0)
            k -= 2;
        else
            k -= 1;
    }
    else
        k = x;

    for (; c <= k; c += 2)
    {
        for (; i <= c; i++)
            obekt[i].String();
        i -= 2;
        for (; i >= 1; i--)
            obekt[i].String();
        i = +1;
    }
}

void part2(myclass *obekt, int y)
{
    for (int i = 1; i <= y; i++)
        obekt[i].String();
}

void part3(myclass *obekt, int y)
{
    int c = 2,
        i = y,
        k = y;
        k -= 1;

    for (; c <= k; c += 2)
    {
        for (; i > c-1; i--)
            obekt[i].String();
        i += 2;
        for (; i <= y; i++)
            obekt[i].String();
        i = y;
    }
}

void part4(myclass *obekt, int y)
{
    for (int i = 1; i < y; i++)
        obekt[i].String();
    for (int i = y; i > 1; i--)
        obekt[i].String();
}

void part5(myclass *obekt, int y)
{
    int i = 1;
    for (int c = 1; c <= y; c += 2)
    {
        for (; i <= y; i++)
            obekt[i].String();
        i -= 1;
        for (; i > c+2; i--)
            obekt[i].String();
        i = c + 2;
    }
}

void part6(myclass *obekt, int x, int y)
{
    bool vipadok = 0;
    int i = y + 1,
        c = 2;
    if (y % 2 == 0)
        obekt[1].String();
    while (i <= x)
    {
        if (y % 2 != 0 || (y % 2 == 0 && vipadok == 1))
        {
            for (int j = i; j >= c; j--)
                obekt[j].String();
            c += 1;
            i += 1;
        }
        if (i > x)
            return;
        else
            for (int j = c; j <= i; j++)
                obekt[j].String();
        i += 1;
        c += 1;
        vipadok = 1;
    }
}

void part7(myclass *obekt, int x, int y)
{
    int i = y,
        k = x;
    bool vipadok = 0;
    while (x >= i)
    {
        if (x % 2 == 0 || x % 2 != 0 && vipadok == 1)
            for (int j = i; j <= x; j++)
            obekt[j].String();
        if (x % 2 == 0 || x % 2 != 0 && vipadok == 1)
        i += 1;
        for (int j = x; j >= i; j--)
            obekt[j].String();
        i += 1;
        vipadok = 1;
    }
}

void part8(myclass *obekt, int x, int y, bool napramok)
{
    if (napramok == 1)
        for (int j = x; j >= 1; j--)
            obekt[j].String();
    else
        for (int j = 1; j <= x; j++)
            obekt[j].String();
}

void part9(myclass *obekt, int x, int y, bool napramok)
{
    if (napramok == 1)
        for (int i = x; i >= y; i--)
            obekt[i].String();
    else
        for (int i = y; i <= x; i++)
            obekt[i].String();
}

void initialization(myclass *obekt, int x, int y)
{
    for (int i = 1; i <= x; i++)
        obekt[i].initialization(y);
}

void cout_String(myclass *obekt, int x, int y)
{
    for (int i = 1; i <= x; i++)
        obekt[i].cout_String(y);
}

int main()
{
    double  x, y;
    cout << "Enter x , y ->";
    cin >> x >> y;
    if (x != (int)x || y != (int)y || x <= 0 || y <= 0)
    {
        cout << "Error!";
        getch();
        return -1;
    }
    myclass *obekt;
    if (x >= y)
        obekt = new myclass[(int)x + 1];
    else
        obekt = new myclass[(int)y + 1];
    initialization(&obekt[0], x, y);
    part1(&obekt[0], y, x);
    if (y == x)
    {
        if ((int)y % 2 != 0)
        {
            part2(&obekt[0], y);
            part3(&obekt[0], y);
        }
        else
        {
            part4(&obekt[0], y);
            part5(&obekt[0], y);
        }
    }
    else
    {
        if (x > y)
        {
            if ((int)x % 2 == 0)
            {
                if ((int)y % 2 != 0)
                    part2(&obekt[0], y);
                else
                    part4(&obekt[0], y);

                part6(&obekt[0], x, y);

                if ((int)y % 2 != 0)
                    part7(&obekt[0], x, (x - y) + 2);
                else
                    part7(&obekt[0], x, (x - y) + 2);
            }
            else
            {
                if ((int)y % 2 != 0)
                    part2(&obekt[0], y);
                else
                    part4(&obekt[0], y);;

                part6(&obekt[0], x, y);

                if ((int)y % 2 != 0)
                    part7(&obekt[0], x, (x - y) + 2);
                else
                    part7(&obekt[0], x, (x - y) + 2);
            }
        }
        else
        {
            if ((int)x % 2 == 0)
            {
                bool napramok;
                for (int i = x; i < y; i++)
                {
                    if (i % 2 == 0)
                        napramok = 0;
                    else
                        napramok = 1;
                    part8(&obekt[0], x, y, napramok);
                }
                if ((int)y % 2 == 0)
                    for (int i = 2; i < y; i++)
                    {
                    if (i % 2 == 0)
                        napramok = 0;
                    else
                        napramok = 1;
                    part9(&obekt[0], x, i, napramok);
                    }
                else
                    for (int i = 2; i < y; i++)
                    {
                    if (i % 2 != 0)
                        napramok = 0;
                    else
                        napramok = 1;
                    part9(&obekt[0], x, i, napramok);
                    }
            }
            else
            {
                bool napramok;
                for (int i = x; i < y+1; i++)
                {
                    if (i % 2 == 0)
                        napramok = 1;
                    else
                        napramok = 0;
                    part8(&obekt[0], x, y, napramok);
                }
                if ((int)y % 2 == 0)
                    for (int i = 2; i < y; i++)
                    {
                    if (i % 2 == 0)
                        napramok = 0;
                    else
                        napramok = 1;
                    part9(&obekt[0], x, i, napramok);
                    }
                else
                    for (int i = 2; i < y; i++)
                    {
                    if (i % 2 != 0)
                        napramok = 0;
                    else
                        napramok = 1;
                    part9(&obekt[0], x, i, napramok);
                    }
            }
        }
    }
    cout_String(&obekt[0], x, y);
    getch();
    return 0;
}

4 Востаннє редагувалося Arete (23.07.2014 12:49:20)

Re: Заповнити двовимірний масив зигзагом по діагоналі

Привіт!

Спробував вирішити задачку...
Основна ідея така:
1. вводиться поняття діагональ масиву - це ті діагоналі по яким послідовно розміщуються елементи.
2. кожна діагональ має:

  • індекс (порядковий номер);

  • довжину (кількість елементів в діагоналі);

  • максимальний елемент (величина максимального елемента в діагоналі);

  • напрямок (напрямок збільшення величини елементів - зверху-вниз або знизу-вверх);

  • тип (визначається по розміру діагоналі - зростаюча, максимальна, спадаюча);

  • верхня точка (координати верхнього елементу діагоналі)

3. є клас "Array2d" двомірного масиву (з масивом діагоналей).


Алгоритм вставки елемента в масив:
1. шляхом зрівняння значення елемента та максимального значення елемента кожної діагоналі, знаходиться та діагональ в яку цей елемент входить;
2. визначається різниця значення заданого елементу та значення верхнього елементу діагоналі;
3. зміщуємось по діагоналі від верхньої точки "вниз" на цю різницю;
4. записуємо значення елементу в знайдену точку на діагоналі.


Алгоритм роботи програми:
1. задається розмір масиву;
2. записуються в масив значення його елементів;
3. масив виводиться на екран.

Код програми поділений на 4 "секції": діагоналі, масив "Array2d", функції введення цілих чисел, функція main.


З.І. Буду радий почути запитання та конструктивну критику :) Є ще одна ідея щодо то як розв'язати цю задачу. Пізніше спробую реалізувати.

Малюнок діагоналей:

Прихований текст
http://s019.radikal.ru/i641/1407/34/252c89a82889.jpg


Код програми:

Прихований текст

#include <iostream>
#include <string>
#include <stdlib.h> 
#include <iomanip>

//********************************************************************
// DIAGONAL ENTITY
//
// Class Diagonal and his functions
//********************************************************************

// Diagonal type
enum DiagType {INCREASE, MAXIMUM, DECREASE};
// Diagonal direction
enum DiagDirect {BOTTOM_TOP, TOP_BOTTOM};

// Simple coordinates
struct Coordinates {
  int x;
  int y;
  Coordinates() : x(0), y(0){}
};

//--------------------------------------------------------------------
// Diagonal count in a 2d-array h * m size
//--------------------------------------------------------------------
inline int DiagonsCount( const int& h, const int& w ) {
  return h + w - 1;
}

//--------------------------------------------------------------------
// Diagonal max length in a 2d-array h * m size
//--------------------------------------------------------------------
inline int DiagonMaxLength( const int& h, const int& w ) {
  return h < w ? h : w;
}

//--------------------------------------------------------------------
// Count diagonal wih max lenght in a 2d-array h * m size
//--------------------------------------------------------------------
inline int DiagonsMaxLengthCount( const int& h, const int& w ) {
  return abs( h - w ) + 1;
}

//--------------------------------------------------------------------
// Diagonal #index type in a 2d-array h * m size
//--------------------------------------------------------------------
DiagType DiagonType( const int& h, const int& w, const int& index ) {
  int maxLength = DiagonMaxLength( h, w );
  if ( ( index + 1 ) < maxLength )
    return INCREASE;
  else if ( ( index + 1 ) <= maxLength + DiagonsMaxLengthCount( h, w ) - 1 )
    return MAXIMUM;
  else
    return DECREASE;
}

//--------------------------------------------------------------------
// Diagonal #index length in a 2d-array h * m size
//--------------------------------------------------------------------
int DiagonLength( const int& h, const int& w, const int& index ) {
  switch ( DiagonType( h, w, index ) ) {
    case INCREASE: return index + 1;
    case MAXIMUM: return DiagonMaxLength( h, w );
    case DECREASE: return DiagonsCount( h, w ) - index;
  }
}

//--------------------------------------------------------------------
// Diagonal #index top element coordinates in a 2d-array
//--------------------------------------------------------------------
void DiagonTop( const int& width, const int& index, Coordinates& coor ) {
  int correction = ( index + 1 ) - width;
  correction = correction > 0 ? correction : 0;
  if ( correction )
    coor.x = width - 1;
  else
    coor.x = index;
  coor.y = correction;
}

//--------------------------------------------------------------------
// Diagonal entity class
//--------------------------------------------------------------------
class Diagonal {
public:
  Diagonal(); // default constructor
  Diagonal( const Diagonal&, const int&, const int& ); // constructor
  int Index() const { return _index; } // index in a 2d-array
  int Length() const { return _length; } // count of elements
  int MaxElement() const { return _maxelement; } // max element value
  Coordinates Top() const { return _top; } // coordinates top element
  DiagDirect Direction() const { return _direction; } // up-down, down-up
  DiagType Type() const { return _type; } // increase, maximum length, decrease
private:
  Diagonal( const Diagonal& ){}; // hidden copy constructor
  int _index;
  int _length;
  int _maxelement;
  Coordinates _top;
  DiagDirect _direction;
  DiagType _type;
};

//--------------------------------------------------------------------
// Default constructor - creates first diagonal 2d-array
//--------------------------------------------------------------------
Diagonal::Diagonal() :
  _index(0),
  _length(1),
  _maxelement(1),
  _top(),
  _direction(TOP_BOTTOM),
  _type(INCREASE)
{}

//--------------------------------------------------------------------
// Constructor - creates NEXT diagonal using input diagonal data
//--------------------------------------------------------------------
Diagonal::Diagonal( const Diagonal& diagonal, const int& height, const int& width ) {
  _index = diagonal.Index() + 1;
  _type = DiagonType( height, width, Index() );
  _length = DiagonLength( height, width, Index() );
  _maxelement = diagonal.MaxElement() + Length();
  _direction = diagonal.Direction() == TOP_BOTTOM ? BOTTOM_TOP : TOP_BOTTOM;
  DiagonTop( width, Index(), _top );
}

//--------------------------------------------------------------------
// Indicates whether element belongs diagonal
//--------------------------------------------------------------------
bool DiagHasElement( const Diagonal& diagonal, const int& element ) {
  int minElement = diagonal.MaxElement() - diagonal.Length() + 1;
  return ( element >= minElement ) && ( element <= diagonal.MaxElement() );
}


//--------------------------------------------------------------------
// Returns element coordinates if it belongs diagonal, otherwise -1,-1
//--------------------------------------------------------------------
bool DiagElementCoor( const Diagonal& diagonal, const int& element, Coordinates& coor ) {
  if ( DiagHasElement( diagonal, element ) ) {
    int topElement = 0;
    if ( diagonal.Direction() == TOP_BOTTOM )
      topElement = diagonal.MaxElement() - diagonal.Length() + 1;
    else
      topElement = diagonal.MaxElement();
    int correction = abs( topElement - element );
    coor = diagonal.Top();

    coor.x -= correction;
    coor.y += correction;
  }
  else
    coor.x = coor.y = -1;
}


//********************************************************************
// ARRAY2D ENTITY
//
// Class Array2d, containes 2-dimentional array
//********************************************************************


//--------------------------------------------------------------------
// Array2d entity class
//--------------------------------------------------------------------
class Array2d {
public:
  Array2d( const int&, const int& ); // default constructor
  ~Array2d(); // destructor
  int Height() const { return _height; }
  int Width() const { return _width; }
  int Item( const int& x, const int& y ) const { return _array[x][y]; }
  void SetItem( const int& ); // set value to some item
  class exc_out_of_range{}; // out of range exception
private:
  Array2d( const Array2d& ){}; // hidden copy constructor
  Array2d operator= ( const Array2d& ) {}; // hidden assing operation
  int _height;
  int _width;
  int** _array;
  Diagonal* _diagonals;
};


//--------------------------------------------------------------------
// Default constructor - creates 2d-array, filled with 0, and diagonal array
// Bad example - might be raised bad_alloc exception
//--------------------------------------------------------------------
Array2d::Array2d( const int& a, const int& b ) : _height(a), _width(b) {
  _array = new int* [ Width() ];
  for ( int i = 0; i < Width(); ++i )
    _array[i] = new int[ Height() ];

  for ( int i = 0; i < Height(); ++i ) {
    for ( int j = 0; j < Width(); ++j ) {
      _array[j][i] = 0;
    }
  }

  int count = DiagonsCount( Height(), Width() );
  _diagonals = new Diagonal[ count ];
  _diagonals[0] = Diagonal();
  for ( int i = 1; i < count; ++i )
    _diagonals[i] = Diagonal( _diagonals[ i-1 ], Height(), Width() );  
}

//--------------------------------------------------------------------
// Destructor - destroys 2d-array and diagonal array
//--------------------------------------------------------------------
Array2d::~Array2d() {
  for ( int i = 0; i < Width(); ++i )
    delete[] _array[i];
  delete[] _array;
  delete[] _diagonals;
}

//--------------------------------------------------------------------
// Operator << - showes 2d-array with intendation
//--------------------------------------------------------------------
std::ostream& operator<< ( std::ostream& o, const Array2d& a ) {
  float d = a.Height()*a.Width();
  int intend = 0;
  while ( d > 1 ) {
    ++intend;
    d /= 10;
  }
  for ( int i = 0; i < a.Height(); ++i ) {
    for ( int j = 0; j < a.Width(); ++j )
      o << std::setw( intend ) << a.Item( j,i ) << ' ';
    o << std::endl;
  }
}

//--------------------------------------------------------------------
// Sets value element to some item in the 2d-array
//--------------------------------------------------------------------
void Array2d::SetItem( const int& element ) {
  if ( ( element <= 0 ) || ( element > Height() * Width() ) )
    throw exc_out_of_range();

  int count = DiagonsCount( Height(), Width() );
  int index;
  for ( index = 0; index < count; ++index ) {
    if ( DiagHasElement( _diagonals[ index ], element ) )
      break;
  }
  Coordinates c;
  DiagElementCoor( _diagonals[ index ], element, c );
  _array[c.x][c.y] = element;
}

//********************************************************************
// INPUT INTEGET FUNCTIONS
//
// Input integer from cin functions
//********************************************************************

class exc_bad_int{};

//--------------------------------------------------------------------
// Indicates whether string can be NONNEGATIVE integer
//--------------------------------------------------------------------
bool IsDigits( const std::string& str ) {
  std::string::const_iterator iter = str.begin();
  for ( iter; iter != str.end(); ++iter )
    if ( !( isdigit( *iter ) ) )
      return false;
  return true;
}

//--------------------------------------------------------------------
// Translates string to NONNEGATIVE integer. Exception exc_bad_int could be raised
//--------------------------------------------------------------------
int StringToInt( const std::string& str ) {
  if ( !( IsDigits( str ) ) )
    throw exc_bad_int();
  return atoi( str.c_str() );
}

//--------------------------------------------------------------------
// Returns NONNEGATIVE integer from cin
//--------------------------------------------------------------------
int IntegerIntput() {
  bool input = false;
  int i = 0;
  std::string str;
  while ( true ) {
    std::cin >> str;
    try {
      i = StringToInt( str );
      return i;
    }
    catch( exc_bad_int ) {
      std::cout << "Error: value is not positive integer." << std::endl;
    }
  }
}


//********************************************************************
// MAIN SECTION
//********************************************************************
int main( int argc, char **argv ) {
  std::cout << "Input array height:" << std::endl;
  int height = IntegerIntput();
  std::cout << "Input array width:" << std::endl;
  int width = IntegerIntput();

  Array2d a( height, width );

  int count = height * width;
  for ( int i = 1; i <= count; ++i )
    a.SetItem( i );
  std::cout << a;

  return 0;
}

life is too short to remove usb safely

5

Re: Заповнити двовимірний масив зигзагом по діагоналі

Якщо комусь цікаво - рішення, що потребує O(1) пам'яті. Масив не створюється, програма за координатами (x,y) обчислює значення цього елемента.

Прихований текст

#include <iostream>
#include <iomanip>

using namespace std;

class ZigzagArray
{
  int m, n, firstEdge, secondEdge, leftTriangleSum, totalSum; 
  
  int firstSection ( int x, int y );
  int secondSection( int x, int y );
  int thirdSection ( int x, int y );
  
  public:
  int at( int x, int y );
  ZigzagArray( int m_, int n_ );
};

int ZigzagArray::firstSection( int x, int y )
{
  int base = ( x + y ) * ( x + y + 1 ) / 2 + 1;
  if( ( x + y ) % 2 == 0 )
    return base + x;
  else
    return base + y;
}

int ZigzagArray::secondSection( int x, int y )
{
  int base = leftTriangleSum + ( x + y - firstEdge ) * firstEdge + 1;
  if( ( x + y ) % 2 == 0 )
    return base + ( m > n ? firstEdge - y - 1 : x );
  else
    return base + ( n > m ? firstEdge - x - 1  : y);;
}

int ZigzagArray::thirdSection( int x, int y )
{
  return totalSum - at( m - x - 1, n - y - 1) + 1;
}

ZigzagArray::ZigzagArray( int m_, int n_ ) : 
  m( m_ ), n( n_ ),
  firstEdge  ( min ( m, n ) ),
  secondEdge ( max ( m, n ) ),
  leftTriangleSum ( firstEdge * ( firstEdge + 1 ) / 2 ),
  totalSum ( m * n )
{
}

int ZigzagArray::at( int x, int y )
{
  if      ( x + y < firstEdge )
    return firstSection ( x, y );
  else if ( x + y < secondEdge )
    return secondSection( x, y );
  else
    return thirdSection ( x, y );
}

int main()
{
  int m, n;
  cin >> m >> n;
  if( !cin || ( m <= 0 ) || ( n <= 0 ) )
  {
    cout << "Error!" << endl;
    return 1;
  }
  
  ZigzagArray zigzagArray( m, n );
  
  for( int i = 0; i < m; ++i )
  {
    for( int j = 0; j < n; ++j )
      cout << setw( 5 ) << zigzagArray.at( i, j );
    cout << endl;
  }
}

6

Re: Заповнити двовимірний масив зигзагом по діагоналі

Привіт!

Ще один варіант розв’язання.
Ідея заключається в тому щоб уявити "чоловічка", який "ходить" по траєкторії розстановки чисел за певними правилами :)
Маємо такі поняття:

  • чоловічок - начальна точка

  • напрямки руху  - верх, вниз, вліво, вправо, вліво-вверх, вліво-вниз, вправо-вверх, вправо-вниз

  • положення чоловічка на карті - біля стіни (їх чотири), в центрі (будь-де не біля стіни), за територією (помилкова ситуація)

  • крок - координати положення (кінцеві), та напрямок руху

Правила руху:

  • рух вздовж стіни -  чоловічок знаходиться біля стіни, його попередній крок був не вздож стіни - крок вздовж стіни;

  • рух від стіни -  чоловічок знаходиться біля стіни і його попередній крок був вздож стіни - крок від стіни;

  • рух в центрі - якщо чоловічок знаходиться НЕ біля стіни - крок в тому ж самому напрямку в якому йшов до цього;

Напрямки:

  • вздовж лівої і правої стіни -  крок вниз;

  • вздовж верхньої та нижньої стіни -  крок вправо;

  • від лівої і нижньої стіни -  крок вправо-вверх;

  • від правої і верхньої стіни -  крок вліво-вниз;

Стіни мають пріоритет, для того щоб в кутку визначитись вздовж/від якої саме стіни рухатись далі.

Малюнок:
http://s43.radikal.ru/i101/1407/b1/9be943779098.jpg

Код програми:

Прихований текст

#include <iostream>
#include <string>
#include <stdlib.h> 
#include <iomanip>

//********************************************************************
// DIRECTION ENTITY
//
// Direction and poritions functions
//********************************************************************

// Podition type
enum Position { CENTER, LEFT_WALL, BOTTOM_WALL, TOP_WALL, RIGHT_WALL, OUT_OF_TERRITORY };
// Direction type
enum Direction { DOWN, UP, LEFT, RIGHT, DOWN_LEFT, DOWN_RIGTH, UP_LEFT, UP_RIGHT, NONE };

//--------------------------------------------------------------------
// Reverse direction
//--------------------------------------------------------------------
Direction Back (Direction direction) {
  switch ( direction ) {
    case DOWN: return UP;
    case UP: return DOWN;

    case LEFT: return RIGHT;
    case RIGHT: return LEFT;

    case DOWN_LEFT: return UP_RIGHT;
    case UP_RIGHT: return DOWN_LEFT;

    case UP_LEFT: return DOWN_RIGTH;
    case DOWN_RIGTH: return UP_LEFT;

    default: return NONE;
  }
}

//--------------------------------------------------------------------
// Returns direction away from wall. If no any wall returs NONE direction
//--------------------------------------------------------------------
Direction GoAwayFromWall(Position position) {
  switch ( position ) {
    case LEFT_WALL:
    case BOTTOM_WALL:
      return UP_RIGHT;
    case TOP_WALL:
    case RIGHT_WALL:
      return DOWN_LEFT;
    default:
      return NONE;
  }
}

//--------------------------------------------------------------------
// Returns direction along the wall. If no any wall returs NONE direction
//--------------------------------------------------------------------
Direction GoAlongWall(Position position) {
  switch ( position ) {
    case LEFT_WALL:
    case RIGHT_WALL:
      return DOWN;
    case TOP_WALL:
    case BOTTOM_WALL:
      return RIGHT;
    default:
      return NONE;
  }
}

// Simple coordinates
struct Coordinates {
  int x;
  int y;
  Coordinates() : x(0), y(0){}
};

//--------------------------------------------------------------------
// Returns position type
//--------------------------------------------------------------------
Position WhereAmI ( const Coordinates& point, const int& height, const int& width ) {

  if ( ( width - point.x < 1 ) || ( height - point.y < 1 ) )
    return OUT_OF_TERRITORY;

  if ( width - point.x == 1 )
    return RIGHT_WALL;

  if ( point.y == 0 && point.x != 0 )
    return TOP_WALL;

  if ( height - point.y == 1 )
    return BOTTOM_WALL;

  if ( point.x == 0 )
    return LEFT_WALL;

  return CENTER;
}

// Step
struct Step {
  Coordinates point; // end point
  Direction direction;
  Step() : point(), direction( NONE ){}
};


// Forward declaration
Step DoStep(const Coordinates& coordinates, const Direction& direction);

//--------------------------------------------------------------------
// Indicates whether was previous step along the wall
//--------------------------------------------------------------------
bool AlongWall(const Step& step, const int& height, const int& width) {
  Step prev_step = DoStep ( step.point, Back( step.direction ) );
  Position position = WhereAmI(prev_step.point, height, width);

  return 
  ( ( ( position == LEFT_WALL ) || ( position == RIGHT_WALL ) ) && ( step.direction == DOWN ) )
  ||
  ( ( ( position == BOTTOM_WALL ) || ( position == TOP_WALL ) ) && ( step.direction == RIGHT ) )
    ;
}

class out_of_territory{};

//--------------------------------------------------------------------
// Returns direction to next step
//--------------------------------------------------------------------
Direction Desicion( const Step& step, const int& height, const int& width ) {
  Position position = WhereAmI( step.point, height, width );

  if ( position == OUT_OF_TERRITORY )
    throw out_of_territory();

  if ( step.direction != NONE ) {
    if ( position == CENTER )
      return step.direction;
    else {
      if ( AlongWall( step, height, width ) )
    return GoAwayFromWall( position );
      else
    return GoAlongWall( position );
    }
  }
  else {
    if ( position == CENTER )
      return UP_LEFT;
    else
      return GoAlongWall( position );
  }
}

//--------------------------------------------------------------------
// Changes coordinates according direction. Returns new step
//--------------------------------------------------------------------
Step DoStep(const Coordinates& coordinates, const Direction& direction) {
  Coordinates coor = coordinates;
  switch ( direction ) {
    case DOWN: { 
      ++coor.y;
      break;
    }
    case UP:{ 
      --coor.y;
      break;
    }
    case LEFT: {
      --coor.x;
      break;
    }
    case RIGHT: {
      ++coor.x;
      break;
    }
    case DOWN_LEFT: {
      --coor.x;
      ++coor.y;
      break;
    }
    case UP_RIGHT: {
      ++coor.x;
      --coor.y;
      break;
    }
    case UP_LEFT: {
      --coor.x;
      --coor.y;
      break;
    }
    case DOWN_RIGTH: {
      ++coor.x;
      ++coor.y;
      break;
    }
    default:;
  }

  Step step;
  step.point = coor;
  step.direction = direction;

  return step;
}


//********************************************************************
// ARRAY2D ENTITY
//
// Class Array2d, containes 2-dimentional array
//********************************************************************


//--------------------------------------------------------------------
// Array2d entity class
//--------------------------------------------------------------------
class Array2d {
public:
  Array2d( const int&, const int& ); // default constructor
  ~Array2d(); // destructor
  int Height() const { return _height; }
  int Width() const { return _width; }
  int Item( const int& x, const int& y ) const { return _array[x][y]; }
  void SetItem( const int&, const int&, const int&);
  class exc_out_of_range{}; // out of range exception
private:
  Array2d( const Array2d& ){}; // hidden copy constructor
  Array2d operator= ( const Array2d& ) {}; // hidden assing operation
  int _height;
  int _width;
  int** _array;
};

//--------------------------------------------------------------------
// Default constructor - creates 2d-array, filled with 0, and diagonal array
// Bad example - might be raised bad_alloc exception
//--------------------------------------------------------------------
Array2d::Array2d( const int& a, const int& b ) : _height(a), _width(b) {
  _array = new int* [ Width() ];
  for ( int i = 0; i < Width(); ++i )
    _array[i] = new int[ Height() ];

  for ( int i = 0; i < Height(); ++i ) {
    for ( int j = 0; j < Width(); ++j ) {
      _array[j][i] = 0;
    }
  }
}

//--------------------------------------------------------------------
// Destructor - destroys 2d-array and diagonal array
//--------------------------------------------------------------------
Array2d::~Array2d() {
  for ( int i = 0; i < Width(); ++i )
    delete[] _array[i];
  delete[] _array;
}

//--------------------------------------------------------------------
// Operator << - showes 2d-array with intendation
//--------------------------------------------------------------------
std::ostream& operator<< ( std::ostream& o, const Array2d& a ) {
  float d = a.Height()*a.Width();
  int intend = 0;
  while ( d > 1 ) {
    ++intend;
    d /= 10;
  }
  for ( int i = 0; i < a.Height(); ++i ) {
    for ( int j = 0; j < a.Width(); ++j )
      o << std::setw( intend ) << a.Item( j,i ) << ' ';
    o << std::endl;
  }
}

//--------------------------------------------------------------------
// Sets [x][y] item by value
//--------------------------------------------------------------------
void Array2d::SetItem(const int& x, const int& y, const int& value) {
  _array[x][y] = value;
}

//--------------------------------------------------------------------
// Sets array according Desicion directions
//--------------------------------------------------------------------
void SetArray( Array2d& array ) {
  int count = array.Height() * array.Width();
  Step step;
  Direction direction;

  array.SetItem( step.point.x, step.point.y, 1 );
  for ( int i = 2; i <= count; ++i ) {
    direction = Desicion( step, array.Height(), array.Width() );
    step = DoStep( step.point,  direction );
    array.SetItem( step.point.x, step.point.y, i );
  }
}

//********************************************************************
// INPUT INTEGER FUNCTIONS
//
// Input integer from cin functions
//********************************************************************

class exc_bad_int{};

//--------------------------------------------------------------------
// Indicates whether string can be NONNEGATIVE integer
//--------------------------------------------------------------------
bool IsDigits( const std::string& str ) {
  std::string::const_iterator iter = str.begin();
  for ( iter; iter != str.end(); ++iter )
    if ( !( isdigit( *iter ) ) )
      return false;
  return true;
}

//--------------------------------------------------------------------
// Translates string to NONNEGATIVE integer. Exception exc_bad_int could be raised
//--------------------------------------------------------------------
int StringToInt( const std::string& str ) {
  if ( !( IsDigits( str ) ) )
    throw exc_bad_int();
  return atoi( str.c_str() );
}

//--------------------------------------------------------------------
// Returns NONNEGATIVE integer from cin
//--------------------------------------------------------------------
int IntegerIntput() {
  bool input = false;
  int i = 0;
  std::string str;
  while ( true ) {
    std::cin >> str;
    try {
      i = StringToInt( str );
      return i;
    }
    catch( exc_bad_int ) {
      std::cout << "Error: value is not positive integer." << std::endl;
    }
  }
}


//********************************************************************
// MAIN SECTION
//********************************************************************
int main( int argc, char **argv ) {
  std::cout << "Input array width:" << std::endl;
  int width = IntegerIntput();
  std::cout << "Input array height:" << std::endl;
  int height = IntegerIntput();

  Array2d a( height, width );
  SetArray(a);
  std::cout << a;

  return 0;
}

life is too short to remove usb safely
Подякували: Betterthanyou1