Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.78
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,265
29.07.2011, 21:59     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #1
Друзья!
Ввиду возникшей необходимости мной был написан класс "рекурсивный обход матрицы"; Теперь задачи на такую тематику будут решаться легко и просто. С меня интерфейс, с вас- мозги.

подробнее
Рассмотрим одну из таких задач, на её примере я покажу как надо решать такие задачи и познакомлю с терминами. Вот ей текст

....................................................................................
1 Попытка к бегству

Время на тест - 3 секунды.


Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M?N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.
Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника - левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример

Входные данные

3 5
11111
10101
11111

Выходные данные

3

Входные данные

3 5
11101
10101
10101

Выходные данные

impossible
...................................................................................

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

...Кстати, вот эти цепочки:
(4 0) (3 0) (2 0) (1 0) (0 0) (0 1) (0 2) (0 3) (0 4)
(4 0) (3 0) (2 0) (2 1) (2 2) (1 2) (0 2) (0 3) (0 4)
(4 0) (3 0) (2 0) (2 1) (2 2) (2 3) (2 4) (1 4) (0 4)
(4 0) (4 1) (4 2) (3 2) (2 2) (1 2) (0 2) (0 3) (0 4)
(4 0) (4 1) (4 2) (3 2) (2 2) (2 3) (2 4) (1 4) (0 4)
(4 0) (4 1) (4 2) (4 3) (4 4) (3 4) (2 4) (1 4) (0 4)

....................................................................................

Для того чтобы найти такие цепочки необходимо прежде всего создать объект класса
rek_obhod_matr. Перечисляю по порядку параметры, которые он принимает: собственно матрицу,
количество строк, количество столбцов, номер строки и столбца начальной точки.
То есть в нашем случае будет такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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/*и это не все параметры*/)
Пока всё просто. А теперь пошли трудности. Плюсом к перечисленным параметрам в конструктор вы передаёте три СОБСТВЕННЫХ функции.

А взамен получаете вектор векторов пар элементов типа int, каждая пара- координаты очередной точки. Ну то есть вот такую штуку получаете:
C++
1
vector <vector <pair<int, int> > > puti;
(Кстати, размер этого ветора и будет количенство путей, в нашем случае 6, угу?)

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Сосредоточимся на функциях- членах класса
Смотрите. Если мы "стоим" в некоторой клетке, объект, созданный нами называется obhod, то её координаты текущие. Их можно найти с помощью функций-членов:

C++
1
2
int obhod.get_i_tek(); 
int obhod.get_j_tek();
\\\\\\\\\\\\\\\\

Вернёмся к задаче. Представьте себе, что мы каким-то образом (пока неважно, каким, объяснение позже) "добрались" до клетки, например (1, 0) и стоим в ней. Вопрос: какой путь мы прошли? Правильно, вот он: (4, 0) (3, 0) (2, 0)

И возвращается он такой функцией- членом:
C++
1
vector< pair<int, int> > set_chto_proshli ();
...А если мы будем стоять, например в точке (2, 2), то вернётся путь
(4, 0)(3, 0)(2, 0)(2, 1) или (4, 0) (4, 1) (4, 2) (3, 2)

Внимание! Координаты текущей клетки в пройденныё путь не входят!

\\\\\\\\\\\\\\\\

Ещё один вектор, который может нам пригодиться- вектор точек, куда мы можем пойти. Допустим, мы стоим в точке (2, 0). Можем пойти в две точки: (1, 0) или (2, 1)
Вектор этих пар вернёт нам функция-член
C++
1
vector< pair<int, int> > get_kuda_poidom ();
\\\\\\\\\\\\\\\\

Ещё две полезных функции-члена могут нам пригодиться:
Преобразования типа, эта херь позволит перегрузить оператор [][]
Это я сам придумал подачи ребят
C++
1
operator T**() {return matrix;};
Так, а эта функция просто возвращает результат
Это возвращает вектор найденнных путей клеток
C++
1
vector <vector <pair<int, int> > > set_puti () {return puti;}
Ну можно ещё что-нибудь будет добавить при необходимости. Например, возврат количества столбцов, кому охота уж

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

А теперь сосредоточимся на авторских функциях.

111111111111111

Первая функция-предикат, вот её прототип:
C++
1
2
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot);
Она принимает указатель на объект и координаты точки, куда ПОТЕНЦИАЛЬНО можно шагнуть или прыгнуть, кому как охота. Наша задача в этой функции решить подходит ли эта точка для прыжка или нет. Понятное дело, что точка для прыжка должна располагаться рядом с текущей, да не просто рядом а справа или сверху. То есть так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
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)))
  //Тоже щас будет код
 
}
ОК, кроме того в клетке с координатами (i_pot, j_pot) должна быть единица

C++
1
2
3
4
5
6
7
8
9
10
11
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;
}
Вот мы и написали первую функцию предикат

222222222222222222222

Вторая функция-предикат. Необходима для того, чтобы определить- очередной путь закончился или нет? А применительно к нашей задаче- создана ли ЛЮБАЯ из цепочек путей?
Прототип у неё попроще будет, принимает просо указатель на объект

C++
1
2
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source);
Внимание! Путь считается пройденным, если мы "стоим" в некоторой клетке, и она- конец пути.
!!!Помним, что она пока ещё не занесена в пройденный путь!

C++
1
2
3
4
5
6
7
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;            
}
По-моему ничё сложного

3333333333333333333333333

А третья функция изменения. Она нужна для изменения содержания клетки. В данном примере она совсем не нужна. Так как содержимое клеток мы не меняем. Но ниже я приведу пример, когда она нужна. Прототип:
C++
1
2
template <class T>
void izmenenia (rek_obhod_matr<int>* source);
Вот и всё. Теперь скомпонуем всю эту херь в один код. И да, вот окончательный
вариант прототипа конструктора
C++
1
2
3
4
5
6
7
8
9
//Конструктор, принимает такие парамеры: указатель на матрицу,
  //количество строк, количество столбцов
  //начало (строку, столбец)
  //Функцию-предикат отвечающую за то, на какую точку будет совершён переход (прыжок)
  //Функцию- предикат, определяющую, найден ли очередной путь или нет
  //и функцию, меняющую (или не меняющую) матрицу
  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));
А вот весь код будет таким, вывод прилагается
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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;
}
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

И чтобы никто не кговорил, что вот я лох, подогнал клас под одну задачу, представляю ещё две задачи, решённые таким же способом.
Итак, знаменитое заполнение матрицы по спирали, стоим в левом нижнем углу, матрица 6X9
(может быть любая). За содержание функций-предикатов не пинайте, кто может сделать проще пусть напишет проще. Комменты опущу. Тут применяется функция изменения, поскольку мы изменяем клетки, заполняя их числами

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#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;
}
И последняя задача такая: определить все ходы белой шашки.
Значит, у меня белая шашка это единичка, чёрные двойки, остальные ноли. Всё то же самое. Два предиката, пустое изменение, массив, создание объекта и любование результатом.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#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;
}

В классе есть недостатки, так я например не уверен, что всегда надо передавать матрицу в него и делать там копию. Но я для надёжности передаю всё же. В общем, правьте, уточняйте тестируйте. Говорите чё не так, буду исправлять. РАспространяется по лицензии GPL
Миниатюры
предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику   предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику   предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику  

Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 21:59     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Посмотрите здесь:

C++ предлагаю программу людям "альтернативное копирование файлов в проводнике"
C++ предлагаю людям класс "каждому потоку- своё окно" для тестирования многопоточных приложений.
предлагаю людям заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике C++
C++ Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол"
Предлагаю людям класс для написания специфических снимков системы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
29.07.2011, 22:00     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #2
мозк вскипел.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
30.07.2011, 01:16     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #3
kravam, много букв и плохого кода. В чем собственно рекурсивность и в чем собвственно обход?
LosAngeles
Заблокирован
30.07.2011, 06:50     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #4
блин на асме короче можно написать!
Цитата Сообщение от kravam Посмотреть сообщение
РАспространяется по лицензии GPL
кроме тебя это читать никто не будет, а уж тем более разбираться как это работает

Цитата Сообщение от kravam Посмотреть сообщение
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;
}
страх и ужас. Столько кода и всё коту под хвост
Nameless One
30.07.2011, 08:06
  #5

Не по теме:

И да, отучайся уже использовать транслит в идентификаторах

Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 09:05     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #6

Не по теме:

Тут щас будет код
ЛОЛ да и только.)

Да и комменты гениальны!
//Вторая авторская функция-предикат
//И третья функция называется


Преееелесть! Сууупер прееелесть!
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,265
30.07.2011, 15:41  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
kravam, много букв и плохого кода. В чем собственно рекурсивность и в чем собвственно обход?
Рекурсивность реалзована в коде КЛАССА. А код класса я пока не представил. Потому хотя бы, чтобы все оправились от счастья, которое всем свалилось. Пока оцените интерфейс.

Ещё раз: допустим вам необходимо будет решить задачу на рекурсивный обход матрицы. Что это такое я не знаю, в том смысле, что не могу объяснить. Просто иногда задачи такие попадаются.

Так вот. Я избавляю всех от проектирования. Скропайте всего три функции и будет вам счастье. Вот дайте мне какую-нибудь задачу на рекурсивный обход и посмотрите как я её решу. И скажите, нужен такой класс или нет.

...Другой вопрос, что задача будет проста, например: заполнить матрицу значениями элементов индексов строк. Можно и мой класс использовать, но это всё равно, что с топором за мухами гоняться.

/////////////////////////////////////////////

А в чём плохость кода я так и не понял. Или типа на старых дрожжах решили выехать?

Добавлено через 4 минуты
Цитата Сообщение от LosAngeles Посмотреть сообщение
блин на асме короче можно написать!
алё, дядя, что короче-то? Кода класса ты не видел, тах что не хрен п...ть. Задачи, приведённые мной ПРОСТЫ довольно и они всего лишь ПРИМЕР. И не лги, что ты короче напишешь. Знаем асм.

Цитата Сообщение от LosAngeles Посмотреть сообщение
кроме тебя это читать никто не будет, а уж тем более разбираться как это работает
у нас демократия. В натуре путь на асме пишут

Цитата Сообщение от LosAngeles Посмотреть сообщение
Столько кода и всё коту под хвост
не по-мужски. Я сразу сказал- за код не пинать. Можешь сделать короче- сделай короче, я сильно не корпел над ним. Это как пример. Короче, дешёвый авторитет зарабатываешь.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 15:45     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #8
Цитата Сообщение от kravam Посмотреть сообщение
Что это такое я не знаю, в том смысле, что не могу объяснить.
А ты крут! Находишь решение не имея проблемы.)

Ответь на простой вопрос, что там у тебя рекурсивного?
"простой пример с заполнением значений" это итерационная задача. Рекурсия там возможна, но совершенно не к месту.
Если ты не можешь привести в пример класс задач, для которых нужно (или можно) использовать твой класс, то он во первых - бесполезен, а во вторых - реализован с ошибками. Если ты не можешь придумать ни одной такой задачи, то ты ни отладить ни протестировать его не можешь, соответственно и о работоспособности речи никакой быть не может.

А вообще, есть BGL.
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
30.07.2011, 15:49     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #9
Цитата Сообщение от kravam Посмотреть сообщение
А в чём плохость кода я так и не понял.
Ну дык для приличия отформатировал бы его, а если бы покапался в настройках своей IDE то и форматировать не надо, тупо перекопировал и в тэг оформил. И если уж пишешь код для кого-то, так будь добр, дай удобочитаемые(не транслитные) имена функциям, переменным,..etc.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,265
30.07.2011, 15:52  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #10
А класс этот нужен тем, кому по хер на то, как называется задача но кто знает, что она- рекурсивный обход матрицы. Всё. И я действительно крут- я знаю вещи. Правда определение им дать не могу, но прерогативу говорить о названиях вещей я оставляю тебе. Ты-то видать очень хорошо знаешь, что такое рекурсивный обход матрицы...

И алё, там у меня ничего рекурсивного нет. Потому, что рекурсия реализована в КОДЕ КЛАССА. А я его пока не представил.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
30.07.2011, 15:58     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #11
kravam, нельзя ли более тщательно подбирать выражения? Довольно вольная, полунецензурная речь начинает утомлять.

Не по теме:

Цитата Сообщение от kravam Посмотреть сообщение
И алё, там у меня ничего рекурсивного нет. Потому, что рекурсия реализована в КОДЕ КЛАССА. А я его пока не представил.
А я уже представил

Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 15:59     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #12
оК, ты крут. Мы достигли консенсуса.
Сделай в своём классе что либо с матрицей размером 10000х100000 интов. Это всего 1000 мегабайтная матрица. Но что-то мне подсказывает, что в процессе рекурсии ты переполнишь стек гораздо раньше...
LosAngeles
Заблокирован
30.07.2011, 16:01     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от kravam Посмотреть сообщение
И я действительно крут- я знаю вещи
с каких пор писать быдлокод это круто?
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
30.07.2011, 16:04     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #14
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Единственное, за что автора можно похвалить - это за то, что уже начал осознавать, что некоторые прикладные задачи имеют весьма схожие потроха и для реализации этих потрохов можно выделять общие части и накрывать их интерфейсом.

Реализация этой идеи, как мне кажется, полное г...о. Сужу об этом хотя бы потому, что пример задачи, которая решается с помощью этого универсального интерфейса, как-то плохо состыкуется с необходимостью такого интерфейса. Уже из условия задачи можно понять, что при ограничении в M+N-1 ходов нужно найти пути, в которых перемещения только "вправо" и "вверх", предполагая, что узник слева снизу, а выход справа сверху. Т.е. задачу решать надо перебором кобинаций "вверх" и "вправо", а не перебором матрицы. И решить её "в лоб" будет намного быстрее и понятнее, чем с использованием дополнительного класса. Другими словами, конкретно в данном случае это напоминает вот такой старый прикол: Какой язык лучше учить?

Ну и попросту надо помнить инженерное правило: чем более универсален интерфейс, тем он менее пригоден к использованию в реальных условиях. И это касается не только программ, но и любого электронного устройства, механического устройства, инструмента и т.п.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,265
30.07.2011, 16:39  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #15
Цитата Сообщение от Deviaphan Посмотреть сообщение
оК, ты крут. Мы достигли консенсуса.
Сделай в своём классе что либо с матрицей размером 10000х100000 интов. Это всего 1000 мегабайтная матрица. Но что-то мне подсказывает, что в процессе рекурсии ты переполнишь стек гораздо раньше...
алё, дядя, я знаю недостатки рекурсии. Тем не менее её использую. А ты не используй никогда. А то вдруг стек переполнишь...

Добавлено через 39 секунд
Цитата Сообщение от LosAngeles Посмотреть сообщение
с каких пор писать быдлокод это круто?
И ты тоже зарабатываешь дешёвый авторитет

Добавлено через 4 минуты
Цитата Сообщение от Evg Посмотреть сообщение
. Т.е. задачу решать надо перебором кобинаций "вверх" и "вправо", а не перебором матрицы. И решить её "в лоб" будет намного быстрее и понятнее, чем с использованием дополнительного класса.
не по-мужски это за счёт старых заслуг выезжать. Дай код который будет быстрее и понятнее и будем разговаривать.
Кстати, быстрее, может и будет, допускаю. Но мы же к асму не скатываемся? И да, у меня в первом предикате перебирается вся матрица. Но! Хотим интерфейс попроще- надо чем-то поступиться, скоростью в данном случае.

Хотя ваше решение несомненно и быстрее и понятнее. Только ваше хорошее у вас в голове, а моё плохое на бумаге. Вся разница

Добавлено через 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
Ну и попросту надо помнить инженерное правило: чем более универсален интерфейс, тем он менее пригоден к использованию в реальных условиях. И это касается не только программ, но и любого электронного устройства, механического устройства, инструмента и т.п.
Это я знаю. Но!

Двойные стандарты. То есть когда мы пользуемся универсальным интерфейсом, это хорошо. А когда kravam- это плохо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 16:41     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #16
Цитата Сообщение от kravam Посмотреть сообщение
Только ваше хорошее у вас в голове, а моё плохое на бумаге. Вся разница
Твоего на бумаге никто не видел...
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,265
30.07.2011, 16:50  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #17
Нет ну почему же- вот я его представил. Не реализацию класса, а решение задачи. А Evg говорит, что его решение быстрее и понятнее. Только оно где-то там!!

Не по теме:

Напоминает мне одну херь: работал я на стройке и замещал стропаля-бухаря. И его не хотели увольнять потому, что он "работу знает". Только вот знал-то он её дома, а я не знал на работе...




Добавлено через 3 минуты
И кстати о термине "рекурсивный обход матрицы". Я тут порылся в памяти, действительно, это чуть ли не мой термин. Просто решая задачи, которые я определял ТАК, наиболее интересные я складывал в папку и её так озаглавливал. А теперь вот решил написать образец для их решения.

Так что термин "рекурсивный обход матрицы" придуман для меня мной. Ну- я писал код для единомышленников. Для тех кто долбит такие задачи.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
30.07.2011, 16:51     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #18
Цитата Сообщение от kravam Посмотреть сообщение
Дай код который будет быстрее и понятнее и будем разговаривать
Найди в инете код, который перебирает все последовательности нулей и единичек. Он занимает не более 20 строк

Цитата Сообщение от kravam Посмотреть сообщение
Но мы же к асму не скатываемся?
"Быстрее" я в первую очередь имел скорость написания программы, а не её скорость работы. Тупой перебор написать быстрее, чем использовать твой класс. А вот для быстроты работы надо в алгоритм вносить небольшие коррективы: т.е. не "получить комбинацию, а потом проверить", а "проверять в процессе получения комбинации, чтобы если первый ход ведёт в закрытую дверь, то все последующие за ним ходы не перебирать".

Теперь представим, что у нас есть универсальный интерфейс, который выдаёт все комбинации. Тупой алгоритм к нему привинтить легко. А более умный алгоритм уже плохо соотносится на уровне интерфейса с универсальным интерфейсом, выдающим комбинации, до тех пор, пока в этом интерфейсе не будет возможности зарубить некоторые ветки сразу же. И в интерфейсе появится костыль. Потом возьмём другую задачу, в которой требуется внести другие коррективы в алгоритм перебора, и так родится второй костыль. Ну и так далее

Цитата Сообщение от kravam Посмотреть сообщение
То есть когда мы пользуемся универсальным интерфейсом, это хорошо. А когда kravam- это плохо
Читай внимательнее. Не "универсальный интерфейс это плохо", а "чем более универсален интерфейс, тем хуже". Разницу чуешь?
Dekio
Фрилансер
Эксперт C++
 Аватар для Dekio
5816 / 1214 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
30.07.2011, 16:53     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #19
Сообщение было отмечено автором темы, экспертом или модератором как ответ
kravam, я вот не понимаю смысла такое "чудо" выкладывать. Что вы хотели этим сделать?
Если вы думали что это сейчас все побегут использовать, то вы очень наивны. Вас похвалили за идею и за то что вы что-то сделали, сами подумали головой. Но если собрались выкладывать свой "супер класс", то нужно слушать много критики, в том числе не приятной или не выкладывать вообще и сидеть счастливым со своим кодом. Но когда критикуют, нужно объективно оценивать ситуацию и думать: "почему плохо критикуют, что надо сделать что бы это исправить?", а не кидаться на всех, показывая свою "манию величия". Судя по коду, именованию переменных, стиле программирования и общения с людьми могу сказать, что свой статус под ником вы носите вполне заслуженно.

Это все мое имхо и обидеть никого я не собирался
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 16:54     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Еще ссылки по теме:

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++
C++ Класс "Графический объект", от которого будут наследоваться классы "круг" и "квадрат"
C++ Описать класс "Контейнер" как объект, предназначенный для транспортировки классов "Строительных блоков"

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
30.07.2011, 16:54     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #20
Цитата Сообщение от kravam Посмотреть сообщение
Ну- я писал код для единомышленников. Для тех кто долбит такие задачи
Если говоришь о задачах во множественном числе, то возьми 3-4 разных задачи и реши их с помощью своего класса. Тебе как минимум станет понятно, как сделать класс универсальным в использовании. Потому как твой класс пока использовался только для решения одной задачи. Лично меня в это решение вникать заломало, потому что букв ну ОЧЕНЬ много. Ну и до кучи реши эти же задачи без своего класса. А ещё лучше - поищи готовые решения, написанные теми, кто шарит, чтобы сравнить, по качеству, по скорости, да и по количеству букв
Yandex
Объявления
30.07.2011, 16:54     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Ответ Создать тему

Метки
быдлокодерство
Опции темы

Текущее время: 02:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru