примеры задач при изучении C++

[Olej]

Хорошая задача для самых начинающих ...

Вводится целое число.
Подсчитайте программно сколько раз в его десятичную запись входит некоторая цифра, скажем 3. Вот и всё условие. Например: 123 -> 1; 54321345 -> 2; 3333 -> 4 и т.д.

Задача очень простая … на уровне средней (сельской ) школы. Но для того, чтобы задачу сделать не совсем уж примитивной – усложним её так:
– предложите несколько (как можно больше) разных способов реализации;
– для каждой реализации сократите запись кода так, чтобы он был, как можно более кратким.

Поехали...

Код: Выделить всё

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   unsigned long long e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   do if( 3 == e % 10 ) n++;
   while( ( e /= 10 ) > 0 );
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Здесь всё решение укладывается в один оператор do … while.
Но, обратим внимание на то, что формулировка “вводится целое число” – это ввод всегда строки, представляющей число (здесь подвох в формулировке задачи). Тогда так:

Код: Выделить всё

#include <iostream>
#include <cstring>
using namespace std;

int main() {
   char e[ 80 ], *p = e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   while( ( p = strchr( p, '3' ) ) != NULL )
      p++, n++;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Или так:

Код: Выделить всё

#include <iostream>
#include <cstring>
using namespace std;

int main() {
   char e[ 80 ];
   unsigned n = 0, i;
   cout << "Ввод числа: ";
   cin >> e;
   for( i = 0; i < strlen( e ); i++ )
      if( e[ i ] == '3' ) n++;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Или так:

Код: Выделить всё

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   string e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   for( string::iterator i = e.begin() ;; n++, i++ )
      if( ( i = find( i, e.end(), '3' ) ) == e.end() ) break;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Как легко видеть, во всех 4-х вариантах всё решение задачи (без ввода исходных данных и вывода результата) осуществляется 1-м оператором цикла.

P.S. Эта задача является очень хорошей иллюстрацией того основополагающего принципа программирования, что любая поставленная задача может быть решена многими и очень разными способами.

[Olej]

Ещё одна очень хорошая задача ... хоть на C, хоть на C++ - здесь без разницы...
Но, поскольку она завязана на потоки, синхронизацию и параллельное выполнение, то я её снесу сюда вот в тему параллельность + синхронизации (примеры).

[Olej]

Ещё одна хорошая задача ... может не столько для практического использования, сколько попрактиковаться: реализация матриц.
Известное дело, что в C матрицы (прямогольные) зачастую реализуются как:

Код: Выделить всё

double **M; // имитирует динамически создаваемый массив M[][]

Или так ... что то же самое:

Код: Выделить всё

double M[][5] = {
   { 1, 2, 3, 4, 5 },
   { 2, 3, 4, 5, 6 },
}; 

Но в C++ матрицу (в любом представлении ... пусть таком как выше) - легко запаковать в класс, который будет представлять тип матриц.

Задача:
- реализовать класс matrix
- представить как можно больше способов внутреннего хранения матрицы
- так, чтобы класс реализовывал, как минимум, возможности: создания, заполнения, 2-мерной индексации, ввод-вывод, присвоения, инициализации ... что там ещё?
Вот так, чтобы все внутренние реализации класса позволяли делать так:

Код: Выделить всё

class matrix {
   // от вас требуется всего лишь здесь ;-)
}

int main() { // а это тестовая программа
   matrix M( 2, 5 );
   for( int r = 0; r < M.row(); r++ )
      for( int c = 0; c < M.col(); c++ ) M[ r ][ c ] = r + c;
   cout << "матрица M[" << M.row() << "," << M.col() << "]=" << endl << M;
   cout << "Вводите матрицу построчно (Enter - конец ввода):" << endl;
   cin >> M;
   cout << "новая матрица M[" << M.row() << "," << M.col() << "]=" << endl << M;
   cout << "присвоение X = M : ";
   matrix X( 3, 3 );
   X = M;
   cout << "X[" << X.row() << "," << X.col() << "]=" << endl << X;
   cout << "инициализация Y( M ) : ";
   matrix Y( M );
   cout << "Y[" << Y.row() << "," << Y.col() << "]=" << endl << Y;
}

А ... ну и чтобы ввод матрицы (с терминала, переадресацией из файла данных, ...) сделать по-людски ... не спрашивая так занудно "введите число столбцов ... введите число строк ....", а как-то вот так:

Код: Выделить всё

Вводите матрицу построчно (Enter - конец ввода):
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
        

- 2 последовательных Enter (окончание строки ввода + пустая строка) - это конец матрицы ... а столбцы и строки пусть там сама программа считает

[Olej]

- реализовать класс matrix

Поехали...

1. matrix = vector< vector<double> > ... и эта таблица является одним из полей (matvio.cc):

Код: Выделить всё

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

typedef vector<double> line;
ostream& operator <<( ostream& out, line& obj ) {
   for( unsigned i = 0; i < obj.size(); i++ ) 
      out << obj[ i ] << ( i == obj.size() - 1 ? "" : ", " );
   return out;
}

class matrix {
private:
   typedef vector<line> table;
   vector< vector<double> > *data;
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й индекс
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ ) (*data)[ r ].clear();
      (*data).clear();
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( void ) {
      ok = true;
      cols = rows = 0;
      data = new table();      
   }
   matrix( int rows, int cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      line l( cols, 0.0 );      
      data = new table( rows, l );      
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new table();      
      cols = m.cols;
      rows = m.rows;
      for( unsigned r = 0; r < rows; r++ )
         data->push_back( (*m.data)[ r ] );
   }
   ~matrix( void ) {
      clean();
      delete data;
   }
   line& operator []( int row ) { return (*data)[ row ]; }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      cols = m.cols;
      rows = m.rows;
      for( unsigned r = 0; r < rows; r++ ) 
         data->push_back( (*m.data)[ r ] );
      return *this;
   } 
   inline void clear( void ) {
      clean();
      cols = rows = 0;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok ) 
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ ) 
         out << (*(obj.data))[ r ] << endl; 
      return out; 
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clear();
   int r = 0;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      int n = 0;
      vector<double> l;
      try { 
         double d;   
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = l.size();
      else if( obj.cols != l.size() ) {
         obj.ok = false;
         return inp;
      }
      obj.data->push_back( l );
      r++;
   }
   obj.rows = r;
   obj.ok = true;
   return inp;
};

#include "main.c"

2. matrix = производный класс от vector< vector<double> > (matiio.cc):

Код: Выделить всё

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

typedef vector<double> line;
ostream& operator <<( ostream& out, line& obj ) {
   for( unsigned i = 0; i < obj.size(); i++ )
      out << obj[ i ] << ( i == obj.size() - 1 ? "" : ", " );
   return out;
}

typedef vector<line> table;

class matrix : protected vector< vector<double> > {
private:
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й индекс
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ ) (*this)[ r ].clear();
      (*this).clear();
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( unsigned rows, unsigned cols ) {
      this->rows = rows;
      this->cols = cols;
      line l( cols, 0.0 );
      for( unsigned r = 0; r < rows; r++ )
         (*this).push_back( l );
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      rows = m.rows;
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         push_back( ( (table)m )[ r ] );
   }
   ~matrix( void ) { clean(); }
   line& operator []( unsigned row ) { return (*(table*)this)[ row ]; }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      rows = m.rows;
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         push_back( ( (table)m )[ r ] );
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      for( unsigned r = 0; r < obj.rows; r++ ) 
         out << ( (table)obj )[ r ] << endl;
      return out; 
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   int r = 0;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      int n = 0;
      vector<double> l;
      try {
         double d;
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = l.size();
      else if( obj.cols != l.size() ) {
         obj.ok = false;
         return inp;
      }
      obj.push_back( l );
      r++;
   }
   obj.rows = r;
   obj.ok = true;
   return inp;
};

#include "main.c"

[Olej]

- реализовать класс matrix

Поехали...

3. matrix = double[] ... одномерное представление (matpio.cc):

Код: Выделить всё

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

class matrix {
public:
   double *data;  // масив [ rows * cols ]
private:
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й тндекс
protected:
   void clean( void ) {
      delete [] data;
      cols = rows = 0;
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( int rows, int cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      data = new double[ rows * cols ];
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new double[ ( rows = m.rows ) * ( cols = m.cols ) ];
      for( unsigned long long i = 0; i < rows * cols; i++ )
         data[ i ] = m.data[ i ];
   }
   ~matrix( void ) { clean(); }
   double* operator []( int row ) { 
      return data + row * cols;
   }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      data = new double[ ( rows = m.rows ) * ( cols = m.cols ) ];
      for( unsigned long long i = 0; i < rows * cols; i++ )
         data[ i ] = m.data[ i ];
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok ) 
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ ) 
         for( unsigned c = 0; c < obj.cols; c++ ) 
            out << obj.data[ r * obj.cols +  c ] << ( c == obj.cols - 1 ? "\n" : ", " );
      return out; 
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   unsigned r = 0;
   vector<double> l;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      unsigned n = 0;
      try { 
         double d;   
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = n;
      else if( obj.cols != n ) {
         obj.ok = false;
         return inp;
      }
      r++;
   }
   obj.data = new double[ ( obj.rows = r ) * obj.cols ];
   for( unsigned long long i = 0; i < obj.rows * obj.cols; i++ )
      obj.data[ i ] = l[ i ];
   obj.ok = true; 
   return inp; 
};

#include "main.c"

4. 3. matrix = double[][] ... - это традиционное представление, идущее от C реализации, и, как оказывается, самое неудобное и громоздкое (mataio.cc):

Код: Выделить всё

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

class matrix {
private:
   double **data;

   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й тндекс
protected:
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ )
         delete [] data[ r ];
      delete [] data;
      cols = rows = 0;
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( unsigned rows, unsigned cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      data = new double*[ rows ];
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new double*[ rows = m.rows ];
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
      for( unsigned r = 0; r < rows; r++ ) 
         for( unsigned c = 0; c < cols; c++ ) 
            data[ r ][ c ] = m.data[ r ][ c ];
   }
   ~matrix( void ) { clean(); }
   double* operator []( int row ) { return data[ row ]; }

   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      data = new double*[ rows = m.rows ];
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
      for( unsigned r = 0; r < rows; r++ ) 
         for( unsigned c = 0; c < cols; c++ ) 
            data[ r ][ c ] = m.data[ r ][ c ];
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok ) 
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ ) 
         for( unsigned c = 0; c < obj.cols; c++ ) 
            out << obj.data[ r ][ c ] << ( c == obj.cols - 1 ? "\n" : ", " );
      return out; 
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   unsigned r = 0;
   vector<double> l;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      unsigned n = 0;
      try {
         double d;
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = n;
      else if( obj.cols != n ) {
         obj.ok = false;
         return inp;
      }
      r++;
   }
   obj.data = new double*[ ( obj.rows = r ) ];
   for( r = 0; r < obj.rows; r++ ) {
      obj.data[ r ] = new double[ obj.cols ];
      for( unsigned c = 0; c < obj.cols; c++ )
      obj.data[ r ][ c ] = l[ r * obj.cols + c ];
   }
   obj.ok = true;
   return inp;
};

#include "main.c"

[Olej]

А ... ну и чтобы ввод матрицы (с терминала, переадресацией из файла данных, ...) сделать по-людски ... не спрашивая так занудно "введите число столбцов ... введите число строк ...."

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./mataio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matiio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matpio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matvio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

[Olej]

Вот подбросили мне задачку...
Она а). и проста по алгоритмике, понятна и б). не так проста в реализации и в). имеет подводные камни и г). использует матрицы, о которых только-что шла речь ...
Формулировка (я её получил на украинском языке, но как-то переведу):

Условие задачи:
Квадратное поле разбито на N полос по N квадратиков. Некоторые квадратики закрашены в жёлтый цвет, среди которых левый верхний квадратик и правый нижний квадратик.
Черепашка, которая находится в левой верхней клетке, мечтает попасть в правую нижнюю.
Определить может ли она переместиться из левого верхнего квадрата в правый нижний, переползая из текущего квадратика только на соседние жёлтые квадратики (квадратики считаются соседними, только если у них одна сторона общая) в каком-либо направлении. Если такие маршруты существуют, то определить длину кратчайшего из них.

Входной файл input.txt содержит:
N – целое число, размер поля, (N<=100);
Таблица розміром N x N с значениями 0 или 1 – структура поля:
1 – закрашенный квадратик; 0 – чистый квадратик.

Выходной файл output.txt содержит одно целое число:
0 – если между указанными квадратиками нет ни единой траектории;
положительное число – минимальное число шагов, если между указанным квадратиками есть хотя бы один маршрут.

Как понятно из формулировки (все вот эти input.txt и output.txt ... для автоматической формальной проверки результата) - это из задач так называемого "спортивного программирования", или олимпиадных задач.

Кроме того, вводить N прежде, как размерность следующей далее матрицы - глупость. Размер матрицы должен извлекаться из её изображения, как делает человек глазами, и как показано в совсем предыдущих сообщениях о матрицах.

[Olej]

в). имеет подводные камни

Подводные камни (не сразу очевидные) таких задач:
1. Должны обрабатываться тупиковые пути, "отростки"...
2. Должны исключаться повторные обходы (кружение до бесконечности) на циклических путях (нужно отслеживать пройденную траекторию).

Как на примере вот такой матрицы:

1 1 1 0 0
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1

[Olej]

проста по алгоритмике, понятна

Всё решение задачи вот:

Код: Выделить всё

int way( matrix& m, int y, int x ) {
   if( y == m.row() - 1 && x == m.col() - 1 ) return 1; // это конечная точка
   matrix m1( m );
   m1[ y ][ x ] = false;                                // отметить как пройдено
   int y1, x1, res = INT_MAX;
   for( int i = 0; i < 4; i++ ) {                       // обойти 4 соседа
      switch( i ) {
         case 0:
            y1 = y; x1 = x + 1; break;
         case 1:
            y1 = y; x1 = x - 1; break;
         case 2:
            y1 = y + 1; x1 = x; break;
         case 3:
            y1 = y - 1; x1 = x; break;
      }
      if( x1 < 0 || x1 >= m.col() ||
          y1 < 0 || y1 >= m.row() ) continue;          // поле за пределами матрицы
      if( !m1[ y1 ][ x1 ] ) continue;                  // недопустиммый шаг
      int ret = way( m1, y1, x1 );
      if( ret > 0 && ret < res )
         res = ret + 1;
   }
   return res == INT_MAX ? 0 : res;
}

А потом где-то в main:

Код: Выделить всё

...
   int w = way( M, 0, 0 );
...

В итоге:

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepah input5_1.txt 
matrix size 5 x 5
matrix M[5,5]=
1, 1, 1, 0, 0
1, 0, 1, 1, 1
1, 0, 1, 0, 0
1, 0, 1, 1, 1
1, 1, 1, 0, 1
trace in 8 steps

Собственно ...
Условия задачи, как они сформулированы - выполнены полностью.
Но вот только для матрицы размером 10х10:

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepah input10_2.txt 
matrix size 10 x 10
matrix M[10,10]=
1, 0, 0, 0, 0, 0, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 0, 0, 1
1, 0, 0, 0, 0, 0, 1, 0, 0, 1
1, 0, 1, 1, 1, 0, 1, 0, 0, 1
1, 0, 1, 0, 0, 0, 1, 0, 0, 1
1, 0, 1, 1, 1, 1, 1, 0, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1
1, 1, 1, 1, 0, 0, 0, 0, 0, 1
0, 0, 0, 1, 1, 1, 1, 1, 1, 1
trace in 18 steps

Здесь отследить эту трассу (из нескольких) из18 шагов - сложно.
А на матрице 50х50, скажем - просто невозможно!

Следующий этап задачи: не только вычислить минимальную трассу, но и диагностировать её ... что-то типа:

Код: Выделить всё

...
trace in 18 steps
<0,0> <1,0> <2,0> <3,0> <4,0> <5,0> <6,0> <7,0> <8,0> <8,1> <8,2> <8,3> <9,3> <9,4> <9,5> <9,6> <9,7> <9,8> <9,9>

Но для этого задача становится намного сложнее!
(Я так подозреваю, что для какого-то-там спортивного программирования её поэтому и сформулироаали именно так)

[Olej]

Но для этого задача становится намного сложнее!

Вот такой код могу предложить:

Код: Выделить всё

...
struct coord {
   int y, x;
   coord( int y, int x ) {
      this->y = y;
      this->x = x;
   }
   coord operator +( coord& s ) {
      return coord( y + s.y, x + s.x );
   };
   coord& operator +=( const coord & s ) {
      y += s.y;
      x += s.x;
      return *this;
   };
   friend ostream& operator <<( ostream& out, coord& obj ) {
      return out << '<' << obj.y << ',' << obj.x << '>';
   }
};
...
list<coord> way( matrix& m, coord& p ) {
   list<coord> v;                                              // пустой список
   if( p.y == m.row() - 1 && p.x == m.col() - 1 ) {            // это конечная точка
      v.push_back( p );
      return v;
   }
   matrix m1( m );
   m1[ p.y ][ p.x ] = false;                                   // отметить как пройдено
   unsigned len = INT_MAX;
   static coord neib[] = { coord( 0, 1 ), coord( 0, -1 ),
                           coord( 1, 0 ), coord( -1, 0 ) };    // соседи
   for( unsigned i = 0; i < sizeof( neib ) / sizeof( neib[ 0 ] ); i++ ) {
      coord p1 = p + neib[ i ];
      if( p1.x < 0 || p1.x >= m.col() ||
          p1.y < 0 || p1.y >= m.row() ) continue;              // поле за пределами матрицы
      if( !m1[ p1.y ][ p1.x ] ) continue;                      // недопустиммый шаг
      list<coord> v1 = way( m1, p1 );                          // последующая трасса
      if( v1.size() > 0 && v1.size() < len ) {                 // это одно из решений
         v1.push_front( p );
         len = v1.size();
         v = v1;
      }
   }
   return v;
}
...

Он не намного бъёмнее ... но с ним пришлось повозиться .

Теперь это выглядит так:

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepahv input20_1.txt 
matrix size 20 x 20
space matrix M[20,20]=
1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1
1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1
1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1
trace in 80 steps
<0,0> <1,0> <1,1> <1,2> <2,2> <2,3> <3,3> <4,3> <4,2> <4,1> <4,0> <5,0> <6,0> <7,0> <8,0> <8,1> <8,2> <8,3> <8,4> <9,4> <10,4> <10,3> <10,2> <10,1> <10,0> <11,0> <12,0> <12,1> <12,2> <12,3> <12,4> <12,5> <13,5> <14,5> <14,4> <14,3> <14,2> <14,1> <14,0> <15,0> <16,0> <16,1> <16,2> <16,3> <16,4> <16,5> <17,5> <18,5> <19,5> <19,6> <19,7> <18,7> <17,7> <16,7> <15,7> <14,7> <13,7> <12,7> <11,7> <10,7> <10,8> <10,9> <11,9> <11,10> <11,11> <12,11> <13,11> <14,11> <15,11> <16,11> <16,12> <16,13> <17,13> <18,13> <19,13> <19,14> <19,15> <19,16> <19,17> <19,18> <19,19> 

Но попробуйте в этой матрице, не имея трассы решения, проверить результат, состоящий в том, что есть таки там трасса из 80 шагов!

P.S. В архиве оба варианта + набор тестовых файлов данных.