предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику

int M, N;
 M= N= 5;
 
 
 //Массив 
 int** array_osn= new int* [M] ;
 
 //ВЫделили память под него и заполнили
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 1;
  }
 }
  array_osn [1] [3]= array_osn [3] [3]= array_osn [3] [1]= array_osn [1] [1]= 0 ;
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, 4, 0/*и это не все параметры*/)

vector <vector <pair<int, int> > > puti;

int obhod.get_i_tek(); 
int obhod.get_j_tek();

vector< pair<int, int> > set_chto_proshli ();

vector< pair<int, int> > get_kuda_poidom ();

operator T**() {return matrix;};

vector <vector <pair<int, int> > > set_puti () {return puti;}

template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot);

template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 //Это вот потенциальная точка справа расположена
 if((i_pot== (*source).get_i_tek())&&(j_pot== ((*source).get_j_tek()+ 1)))
  //Тут щас будет код 
 
 //А эта сверху
 if((j_pot== (*source).get_j_tek())&&(i_pot== ((*source).get_i_tek()- 1)))
  //Тоже щас будет код
 
}

template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
  if((i_pot== (*source).get_i_tek())&&(j_pot== ((*source).get_j_tek()+ 1)))
  if ((*source)[i_pot][j_pot]== 1) {  
   return true;
  }
 if((j_pot== (*source).get_j_tek())&&(i_pot== ((*source).get_i_tek()- 1)))
  if ((*source)[i_pot][j_pot]== 1)  
   return true;
 return false;
}

template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source);

template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 //Тут всё просто. Если текущие координаты 0, 4 значит мы в конце пути
 if (!(*source).get_i_tek() && (*source).get_j_tek()== 4) 
  return true; 
 return false;            
}

template <class T>
void izmenenia (rek_obhod_matr<int>* source);

//Конструктор, принимает такие парамеры: указатель на матрицу,
  //количество строк, количество столбцов
  //начало (строку, столбец)
  //Функцию-предикат отвечающую за то, на какую точку будет совершён переход (прыжок)
  //Функцию- предикат, определяющую, найден ли очередной путь или нет
  //и функцию, меняющую (или не меняющую) матрицу
  rek_obhod_matr(T**, int, int,int, int,  bool(*)(rek_obhod_matr<int>* source, int, int),\
                 bool (*) (rek_obhod_matr<int>* source),\
                 void (*)(rek_obhod_matr<int>* source));

#include <iostream>
#include <windows.h>
using namespace std;
 
 
#include "rek_obhod_matr.h" 
 
 
 
 
//Первая авторская функция-предикат
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 if((i_pot== (*source).get_i_tek())&&(j_pot== ((*source).get_j_tek()+ 1)))
  if ((*source)[i_pot][j_pot]== 1) {  
   return true;
  }
 if((j_pot== (*source).get_j_tek())&&(i_pot== ((*source).get_i_tek()- 1)))
  if ((*source)[i_pot][j_pot]== 1)  
   return true;
 return false;
}
 
//Вторая авторская функция-предикат
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 if (!(*source).get_i_tek() && (*source).get_j_tek()== 4) 
  return true; 
 return false;            
}
 
 
//И третья функция называется
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 int M, N;
 M= N= 5;
 
 
 //Массив тот самый
 int** array_osn= new int* [M] ;
 
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 1;
  }
 }
 array_osn [1] [3]= array_osn [3] [3]= array_osn [3] [1]= array_osn [1] [1]= 0 ;
 
 
 //ВЫведем его
 printf ("сам массив:\n");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++)
   printf ("%d ", array_osn[i][j]);
  printf ("\n");
 };
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, 4, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 
 //А здесь мы венули решение
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 
 
 
 //Тут уже изгаляюсь вывожу пути
 printf ("\nрешение:\n");
 int k= 0;
 for (int i= 0; i< obhod.set_puti().size(); i++) {
  for (int j= 0; j< 9; j++) {
   printf ("(%d %d) ", obhod.set_puti()[i][j].first, obhod.set_puti()[i][j].second);
   if ((!((k+1)%9))&& k) {
    printf ("\n");
   }
   k++;
  }
 }
 
 
 getchar ();
 return 0;
}

#include <iostream>
#include <windows.h>
using namespace std;
 
 
#include "rek_obhod_matr.h" 
 
 
 
 
 
//Вот эта та самая первая функция, над которой полоьзователю придётся покорпеть.
//Принимает указатель на объект координаты точки на которую якобы надо делать ход
//потенциальные то есть i_pot и j_pot
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 //ПОехали условие кропать
 if (!(*source)[i_pot][j_pot]&& !(!i_pot&&!j_pot)) {
 
  //Потенциальая клетка находится над текущей клеткой
  if ((i_pot== (*source).get_i_tek()- 1)&& (j_pot== (*source).get_j_tek())) {
    if (!j_pot) {
     return true;
    }
    else if ((*source)[i_pot+ 1][j_pot- 1]) {
     return true;
    };
  }  
 
  //Потенциальная клетка находится под текущей клеткой
  if ((i_pot== (*source).get_i_tek()+ 1)&& (j_pot== (*source).get_j_tek())) {
   if (j_pot== (9- 1))
    return true;
   else if ((*source)[i_pot][j_pot+ 1]) 
    return true;
  }
  //Потенциальная клетка находтся слева от текущей
  if ((j_pot== (*source).get_j_tek()- 1)&& (i_pot== (*source).get_i_tek())) {
   if (i_pot== (6- 1))
    return true;
   else if ((*source)[i_pot+ 1][j_pot+ 1]) { 
    return true;
   }
 }
  //Потенциальная клетка находтся справа от текущей
  if ((j_pot== (*source).get_j_tek()+ 1)&& (i_pot== (*source).get_i_tek())) {
   if (!i_pot)
    return true;
   else if (((*source)[i_pot- 1][j_pot- 1])||(!(i_pot- 1)&&!(j_pot- 1))) { 
    return true;
   }
  } 
 }
 
 return false;
}
 
//Тут просто
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 if (((*source).set_chto_proshli()).size()== 53) 
  return true; 
 return false;            
}
 
 
//И третья функция называется "izmenenia"
//Если наша задача стоит изменить матрицу (заполнить по спирали элементами и прочая)
//То эта функция должна изменить клетку, которую мы РЕШИЛИ ДОБАВИТЬ В ПУТЬ
//То есть речь идёт о клетке с текущими координатами
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {
 if (!(*source).get_i_tek()&& !(*source).get_j_tek()) 
  (*source)[(*source).get_i_tek()][(*source).get_j_tek()]= 0;
 else {
  (*source)[(*source).get_i_tek()][(*source).get_j_tek()]=\
  (*source)[(*source).set_chto_proshli().back().first][(*source).set_chto_proshli().back().second]+ 1;
 }
}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 int M, N;
 M= 6;
 N= 9;
 
 
 //Массив тот самый
 int** array_osn= new int* [M] ;
 
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 0;
  }
 }
 
 
 //ВЫведем его
 printf ("Вывод \"заполнение матрицы по спирали\"\n");
 printf ("сам массив:\n");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++)
   printf ("%d ", array_osn[i][j]);
  printf ("\n");
 };
 
 rek_obhod_matr<int> obhod (array_osn, M, N, 0, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 vector <pair<int, int> > put= obhod.set_chto_proshli();
 
 printf ("\nрешение:\n");
 int k= 0;
 for (int i= 0; i< put.size(); i++) {
  printf ("(%d %d %d) ", put[i].first, put[i].second, obhod [put[i].first][put[i].second]);
  if ((!((k+1)%9))&& k) {
   printf ("\n");
  }
  k++;
 }
 getchar ();
 return 0;
}

#include <iostream>
#include <windows.h>
using namespace std;
 
 
#include "rek_obhod_matr.h" 
//Это определение ходов белой шашки
 
 
 
 
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 pair <int, int> para (i_pot, j_pot);
 vector< pair<int, int> >:: iterator it;
 it= find (chto_proshli.begin(), chto_proshli.end(), para);
 if (it== chto_proshli.end()) {
 
 
 //Срубаем вправо вниз
 if ((((*source).get_i_tek()+ 2)== i_pot)&& (((*source).get_j_tek()+ 2)== j_pot)&&(!(*source)[i_pot][j_pot])&&\
  ((*source)[(*source).get_i_tek()+ 1][(*source).get_j_tek()+ 1]== 2)) {
  if ((*source)[i_pot- 1][j_pot- 1]== 2)
   if ((*source).set_chto_proshli().size()== 2)
    if (abs((*source).set_chto_proshli()[0].first- (*source).set_chto_proshli()[1].first)== 2)
     return true; 
    else return false;
   else return true; 
 }
 //Срубаем влево вниз
 if ((((*source).get_i_tek()+ 2)== i_pot)&& (((*source).get_j_tek()- 2)== j_pot)&&(!(*source)[i_pot][j_pot])&&\
  ((*source)[(*source).get_i_tek()+ 1][(*source).get_j_tek()- 1]== 2)) {
  if ((*source)[i_pot- 1][j_pot+ 1]== 2)
   if ((*source).set_chto_proshli().size()== 2)
    if (abs((*source).set_chto_proshli()[0].first- (*source).set_chto_proshli()[1].first)== 2)
     return true; 
    else return false;
   else return true; 
 } 
 
 //Срубаем влево вверх
 if ((((*source).get_i_tek()- 2)== i_pot)&& (((*source).get_j_tek()- 2)== j_pot)&&(!(*source)[i_pot][j_pot])&&\
  ((*source)[(*source).get_i_tek()- 1][(*source).get_j_tek()- 1]== 2)) {
  if ((*source)[i_pot+ 1][j_pot+ 1]== 2)
   if ((*source).set_chto_proshli().size()== 2)
    if (abs((*source).set_chto_proshli()[0].first- (*source).set_chto_proshli()[1].first)== 2)
     return true; 
    else return false;
   else return true; 
 }
 
 //Срубаем вправо вверх
 if ((((*source).get_i_tek()- 2)== i_pot)&& (((*source).get_j_tek()+ 2)== j_pot)&&(!(*source)[i_pot][j_pot])&&\
  ((*source)[(*source).get_i_tek()- 1][(*source).get_j_tek()+ 1]== 2)) {
  if ((*source)[i_pot+ 1][j_pot- 1]== 2)
   if ((*source).set_chto_proshli().size()== 2)
    if (abs((*source).set_chto_proshli()[0].first- (*source).set_chto_proshli()[1].first)== 2)
     return true; 
    else return false;
   else return true; 
 }  
 
 
 //Ходим влево вверх
 if ((((*source).get_i_tek()- 1)== i_pot)&& (((*source).get_j_tek()- 1)== j_pot) && ((*source)[i_pot][j_pot]== 0)) {
  if (!(*source).set_chto_proshli().size()) {
   return true; 
  }
 }
 //Ходим вправо вверх
 if ((((*source).get_i_tek()- 1)== i_pot)&& (((*source).get_j_tek()+ 1)== j_pot) && ((*source)[i_pot][j_pot]== 0)) {
  if (!(*source).set_chto_proshli().size()) {
   return true; 
  }
 }
} 
 
 return false;
}
 
 
//Эта будет вторая функция, над которой придётся покорпеть
//Ну то есть тупо: завершён очередной обход или нет
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 if(((*source).get_kuda_poidom().size())== 0)
   return true; 
 return false;            
}
 
 
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 int M, N;
 M= 8;
 N= 8;
 
 
 //Массив тот самый
 int** array_osn= new int* [M] ;
 
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 0;
  }
 }
 
 array_osn [2][1]= array_osn [2][3]=array_osn [4][3]= 2;
 array_osn [5][2]= 1;
 
 //ВЫведем его
 printf ("сам массив:\n");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++)
   printf ("%d ", array_osn[i][j]);
  printf ("\n");
 };
 
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, 5, 2,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 vector <pair<int, int> > put= obhod.set_chto_proshli();
 
 printf ("\nрешение:\n");
 for (int i= 0; i< obhod.set_puti().size(); i++) { 
  for (int j= 0; j< obhod.set_puti()[i].size(); j++)  
   printf ("(%d %d) ", obhod.set_puti()[i][j].first, obhod.set_puti()[i][j].second);
  printf ("\n");
 }
 getchar ();
 return 0;
}