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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.78
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
31.07.2011, 13:22  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #61
Максимальное количество шагов? ни хрена себе, а я чё-то не прочёл там такого...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
31.07.2011, 13:31     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #62
Ну так ты читай, а не посылай всех сразу...
Цитата Сообщение от Evg Посмотреть сообщение
Требуется пройти из левого угла в правый, чтобы путь при этом был не более стольки-то, но при этом чтобы сумма чисел по пути следования была максимальная, при этом если по одной клетке проходим два раза, то второй раз число не засчитывается
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
31.07.2011, 13:40  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #63
Если ты про путь, я подсчитываю не количество пройденных клеток, а их сумму.
Похоже на то, что имелось ввиду всё-таки количество клеток. Но уточнять западло.

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

31221
3122121
312212121

И прочая.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
31.07.2011, 13:49     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #64
Цитата Сообщение от kravam Посмотреть сообщение
Похоже на то, что имелось ввиду всё-таки количество клеток.
Там конкретно сказано "путь". С уроков физики мы помним, что путь и расстояние это разные понятия.
Как нам известно из "описания" твоего класса, задачу в постановке evg ты решить не сможешь, т.к. отсутствует возможность повторного посещения клеток.

Добавлено через 1 минуту
Админы, будьте любезны, первый пост под спойлер спрячьте. Браузер обижается столько мотать.)
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
31.07.2011, 14:00  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #65
Я смогу решить задачу во всякой постановке. Ибо читаем внимательно пост номер один:


________________________________________________________________________
Представьте себе, что мы каким-то образом (пока неважно, каким, объяснение позже) "добрались" до клетки, например (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)

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


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

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

Добавлено через 6 минут
Ходить можно вообще куда угодно. Куда. Угодно. Глупо было бы накладывать на это ограничения в классе (хотя одно ограничение есть -индексы клетки, куда будет совершён прыжок, не должны превышать деинкреминированное количество столбцов и строк и не быть отрицательными)

Другое дело, что надо самому написать предикат N1
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
31.07.2011, 14:09     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #66
Цитата Сообщение от kravam Посмотреть сообщение
Так что я это предусмотрел в своём классе.
оК, молодец. Это я не правильно понял интерфейс класса из-за отсутствия документации.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
31.07.2011, 22:09  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #67
Хз как понятно написать. Вот такая документация.
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
class rek_obhod_matr {
 
 public:
  //Конструктор, принимает такие парамеры: указатель на матрицу,
  //количество строк, количество столбцов
  //начало (строку, столбец)
  //Функцию-предикат отвечающую за то, на какую точку будет совершён переход (прыжок)
  //Функцию- предикат, определяющую, найден ли очередной путь или нет
  //и функцию, меняющую (или не меняющую) матрицу
  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));
 
  //Это понятно что делает, возвращает вектор пройденных клеток
  //Это надо в основном будет для предиката poisk_kletok_
  vector< pair<int, int> > set_chto_proshli ();
 
  //Возвращает вектор клеток, куда можно йпойти.
  //Это надо в основном будет для поиска, не конец ли пути
  vector< pair<int, int> > get_kuda_poidom () {return _kuda_poidom;};
 
  //Преобразования типа, эта херь позволит перегрузить оператор [][]
  //Это я сам придумал подачи ребят
  operator T**() {return matrix;};
 
  //Это возвращает вектор найденнных путей клеток
  //Это надо в основном будет для предиката poisk_kletok_
  vector <vector <pair<int, int> > > set_puti () {return puti;}
 
  //Эти функции возвращают координаты текущей клетки
  int get_i_tek () {return i_tek;}
  int get_j_tek () {return j_tek;}
}

Ещё есть реализация. Ну вот кто разберётся в этом тому дам реализацию. Понятнее не умею написать.

Добавлено через 7 часов 53 минуты
Вот условие задачи: дана прямоугольная матрица, заполненная числами типа int. Необходимо из левого нижнего угла попасть в правый верхний. Сумма пройденный клеток не должна превышать заданного числа, количество ходов неограниченно. Ходить можно в любую сторону только на одну клетку. В одну и ту же клетку можно заходить сколько угодно раз. Не допускается ход из клетки A в клетку B если ранее уже был совершён такой ход. Вот я так решил с помощью моего класса. Матрица 2x3
0 1 2
3 4 5
Ограничение 25. Даёт 145 вариантов.


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
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <windows.h>
#include "rek_obhod_matr.h" 
#include <vector>
#include <numeric> 
#define ogranichenie 25 
#define M  2 
#define N  3 
using namespace std;
 
 
 
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 int i_tek= (* source).get_i_tek();
 int j_tek= (* source).get_j_tek();
 //Значение текущей клетки
 int znach_tek= (*source)[i_tek][j_tek];
 
 //Вектор пройденых пар
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 //найдём верхушку этого вектора
 pair <int, int> para;
 if (chto_proshli.size())
  para= make_pair (chto_proshli.back().first, chto_proshli.back().second);
 
  
 //Сумма пройденных клеток; 
 int sum= 0;
 //Вектор пройденных значений
 vector <int> chto_proshli_;
 for (int i= 0; i< chto_proshli.size(); i++)
  chto_proshli_.push_back ((*source)[chto_proshli[i].first][chto_proshli[i].second]);
 
 chto_proshli_.push_back (znach_tek);
 chto_proshli_.push_back ((*source)[i_pot][j_pot]);
 //Сортирнём
 sort (chto_proshli_.begin(), chto_proshli_.end());
 //Убираем повторы
 vector<int>::iterator it= unique (chto_proshli_.begin(), chto_proshli_.end());
 chto_proshli_.resize (it- chto_proshli_.begin());
 //Сама сумма 
 sum= accumulate(chto_proshli_.begin(), chto_proshli_.end(), sum); 
 
 //Это будет вектор пар клеток. Он нужен вот для чего: в одн и ту же клетку зайти допускается.
 //но повторить прыжок- ни в коем случае.
 //прыжок это всегда две клетки. Их и ищем
 
 vector < pair < pair <int, int>, pair <int, int> > > dve_kletki;
 int temp= chto_proshli.size()- 2;
 for (int i= 0; i<= temp; i++) {
  pair <int, int> temp_0 (chto_proshli[i].first, chto_proshli[i].second);    
  pair <int, int> temp_1 (chto_proshli[i+ 1].first, chto_proshli[i+ 1].second);    
  dve_kletki.push_back (pair <pair <int, int>, pair <int, int> > (temp_0, temp_1));
 }    
 
 //Сверху
 if ((i_tek== i_pot+ 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end())
  if (sum<= ogranichenie) 
   return true;
 }
 
 //Снизу
 if ((i_tek== i_pot- 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
  if (sum<= ogranichenie) { 
   return true;
   }
  }
 }
 
 //слева
 if ((i_tek== i_pot)&& (j_tek== j_pot+ 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) { 
    return true;
   }
  }
 }
 
 //Справа
 if ((i_tek== i_pot)&& (j_tek== j_pot- 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) 
    return true;
  }
 }
 return false;            
}
 
 
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 if((!(* source).get_i_tek())&& ((* source).get_j_tek()== N- 1)) {
  return true; 
 }
 return false;            
}
 
 
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 //Массив тот самый
 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");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn[i][j]= i*M+ j;   
   printf ("%d ", array_osn[i][j]);
  }
  printf ("\n");
 };
 
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, M-1, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 
 printf ("всего путей %d\n", obhod.set_puti().size());
 
 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 ", obhod[obhod.set_puti()[i][j].first] [obhod.set_puti()[i][j].second]);
  printf ("\n");
  getchar ();
 }
 getchar ();
 return 0;
}
Ну то есть там мне дали задачу и сказали тестировать класс, а я её усложнил. Класс протестировал.

Добавлено через 1 минуту
Вот условие задачи: дана прямоугольная матрица, заполненная числами типа int. Необходимо из левого нижнего угла попасть в правый верхний. Сумма пройденный клеток не должна превышать заданного числа, количество ходов неограниченно. Ходить можно в любую сторону только на одну клетку. В одну и ту же клетку можно заходить сколько угодно раз. Не допускается ход из клетки A в клетку B если ранее уже был совершён такой ход. Вот я так решил с помощью моего класса. Матрица 2x3
0 1 2
3 4 5
Ограничение 25. Даёт 145 вариантов.


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
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <windows.h>
#include "rek_obhod_matr.h" 
#include <vector>
#include <numeric> 
#define ogranichenie 25 
#define M  2 
#define N  3 
using namespace std;
 
 
 
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 int i_tek= (* source).get_i_tek();
 int j_tek= (* source).get_j_tek();
 //Значение текущей клетки
 int znach_tek= (*source)[i_tek][j_tek];
 
 //Вектор пройденых пар
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 //найдём верхушку этого вектора
 pair <int, int> para;
 if (chto_proshli.size())
  para= make_pair (chto_proshli.back().first, chto_proshli.back().second);
 
  
 //Сумма пройденных клеток; 
 int sum= 0;
 //Вектор пройденных значений
 vector <int> chto_proshli_;
 for (int i= 0; i< chto_proshli.size(); i++)
  chto_proshli_.push_back ((*source)[chto_proshli[i].first][chto_proshli[i].second]);
 
 chto_proshli_.push_back (znach_tek);
 chto_proshli_.push_back ((*source)[i_pot][j_pot]);
 //Сортирнём
 sort (chto_proshli_.begin(), chto_proshli_.end());
 //Убираем повторы
 vector<int>::iterator it= unique (chto_proshli_.begin(), chto_proshli_.end());
 chto_proshli_.resize (it- chto_proshli_.begin());
 //Сама сумма 
 sum= accumulate(chto_proshli_.begin(), chto_proshli_.end(), sum); 
 
 //Это будет вектор пар клеток. Он нужен вот для чего: в одн и ту же клетку зайти допускается.
 //но повторить прыжок- ни в коем случае.
 //прыжок это всегда две клетки. Их и ищем
 
 vector < pair < pair <int, int>, pair <int, int> > > dve_kletki;
 int temp= chto_proshli.size()- 2;
 for (int i= 0; i<= temp; i++) {
  pair <int, int> temp_0 (chto_proshli[i].first, chto_proshli[i].second);    
  pair <int, int> temp_1 (chto_proshli[i+ 1].first, chto_proshli[i+ 1].second);    
  dve_kletki.push_back (pair <pair <int, int>, pair <int, int> > (temp_0, temp_1));
 }    
 
 //Сверху
 if ((i_tek== i_pot+ 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end())
  if (sum<= ogranichenie) 
   return true;
 }
 
 //Снизу
 if ((i_tek== i_pot- 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
  if (sum<= ogranichenie) { 
   return true;
   }
  }
 }
 
 //слева
 if ((i_tek== i_pot)&& (j_tek== j_pot+ 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) { 
    return true;
   }
  }
 }
 
 //Справа
 if ((i_tek== i_pot)&& (j_tek== j_pot- 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) 
    return true;
  }
 }
 return false;            
}
 
 
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 if((!(* source).get_i_tek())&& ((* source).get_j_tek()== N- 1)) {
  return true; 
 }
 return false;            
}
 
 
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 //Массив тот самый
 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");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn[i][j]= i*M+ j;   
   printf ("%d ", array_osn[i][j]);
  }
  printf ("\n");
 };
 
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, M-1, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 
 printf ("всего путей %d\n", obhod.set_puti().size());
 
 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 ", obhod[obhod.set_puti()[i][j].first] [obhod.set_puti()[i][j].second]);
  printf ("\n");
  getchar ();
 }
 getchar ();
 return 0;
}
Ну то есть там мне дали задачу и сказали тестировать класс, а я её усложнил. Класс протестировал.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 06:17     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #68
Цитата Сообщение от kravam Посмотреть сообщение
Не допускается ход из клетки A в клетку B если ранее уже был совершён такой ход.
Вот это ограничение сводит задачу к четырём путям всего. Т.к. ходы вида А-В-А должны отбрасываться за ненужностью. Мне так кажется. Либо нужно разрешать Повторный проход из А в В.
Не, ну в твоей постановке задача решилась, молодец тогда. Только давай матрицу сделай вменяемого размера. Т.е на несколько порядков больше.
И в реальных задачах никогда и никому не нужны ВСЕ решения. Нужно или наилучшее или приемлемое. Т.е. твой класс должен вернуть всего один путь и, по возможности, кратчайший. Причём, без перебора всех возможных вариантов. Просто по той причине, которую ты сам уже озвучивал: перебрать все варианты может быть не возможно.

Вот тебе постановка задачи: Матрица 100х100, случайно заполненная интами. Найти кратчайший путь из первой точки в последнюю, чтобы сумма значений по пути была максимальной (или близкой к максимальной). При повторном прохождении через клетку её стоимость не учитывается. Повторно переходить можно и из точки и в неё. Ни на длину и на сумму ограничения нет.
Постановка специальна такая, чтобы полным перебором задача была не решаема.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
01.08.2011, 15:25  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #69
Цитата Сообщение от Deviaphan Посмотреть сообщение
Т.к. ходы вида А-В-А должны отбрасываться за ненужностью. Мне так кажется. Либо нужно разрешать Повторный проход из А в В.
Можно
A-B-A

Нельзя:
A-B-A-B, A-B-...A-B


Цитата Сообщение от Deviaphan Посмотреть сообщение
Вот тебе постановка задачи: Матрица 100х100, случайно заполненная интами. Найти кратчайший путь из первой точки в последнюю, чтобы сумма значений по пути была максимальной (или близкой к максимальной). При повторном прохождении через клетку её стоимость не учитывается. Повторно переходить можно и из точки и в неё. Ни на длину и на сумму ограничения нет.
Постановка специальна такая, чтобы полным перебором задача была не решаема.
Максимальное-то задаётся или ВООБЩЕ максимальное? Если вообще (на сумму ограничений нет), тогда я пас. И все пас.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 15:27     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #70
Цитата Сообщение от kravam Посмотреть сообщение
тогда я пас. И все пас.
Разумеется максимальное никому не известно. Именно поэтому в скобочках написано:
Цитата Сообщение от kravam Посмотреть сообщение
(или близкой к максимальной)
Благодаря примечанию в скобочках, задача решаема.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.08.2011, 15:30     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #71
Цитата Сообщение от kravam Посмотреть сообщение
И все пас.
Тут динамическое программирование... Если можно шагать только вправо и вниз, то тривиальное.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
01.08.2011, 15:32  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #72
Если оно неизвестно, то к чему мы стремимся?

А вообще-то мне оно известно. Гугол называется. 10- в сотой степени. Но лучше я пусть буду выглядеть трепачом но искать путь, суммируя значения клеток до гугла- нет уж, увольте.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 15:51     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #73
Цитата Сообщение от kravam Посмотреть сообщение
Если оно неизвестно, то к чему мы стремимся?
Слышал про шахматы? Про стопицот других игр и задач. Почти всегда нужно искать неизвестное. Почти никогда оно не находится. Зато находится нечто, похожее на то, что искалось.
Именно поэтому всегда, повторяю, ВСЕГДА, ищется оптимальное решение, а не наилучшее.
Даже в конечных задачах, часто не ищут наилучшего решения, т.к. оно требует полного перебора всех вариантов. Это просто не приемлемо. Ищут наиболее хорошее решение, которое можно найти за разумный промежуток времени.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
01.08.2011, 16:02  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #74
Порассуждать конечно хорошо, но ты согласись если значение, к которому надо стремиться, не задано, а сумма должна быть максимальной, то для матрицы
1 2
3 4

Путь будет
1243124312431243

И эта цепочка бесконечна. Я и говорю- мой класс для таких задач непригоден.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 16:12     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #75
Я не говорил максимальной, я говорил максимальной или близкой к максимальной.
Т.е. если из 1 надо прийти в 4, то и 1-2-4 и 1-3-4 можно считать оптимальным путём. Доказать обратного ведь не возможно без перебора всех вариантов.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.08.2011, 16:21     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #76
Цитата Сообщение от Deviaphan Посмотреть сообщение
Доказать обратного ведь не возможно без перебора всех вариантов.
Подобные задачи решаются за O(n * m). n - количество строк, m - количество столбцов
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 16:24     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #77
Цитата Сообщение от diagon Посмотреть сообщение
Подобные задачи решаются за O(n * m).
Нет. Сложнее. По условию задачи разрешено повторное посещение узлов.
А вот если повторного посещения нету, то поиском в ширину находится наилучшее решение.
А вот простой поиск в глубину не катит. Только А*, если.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
01.08.2011, 16:46  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #78
Я уже говорил, задача не решаема, у условии есть противоречие:

Допустим, решение 124. Возражение: сумма не максимальна.
А на все другие варианты, как-то:1243124 и так далее, будет такое возражение: сумма не кратчайшая, есть и короче.

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

Я в такие игры не играю.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.08.2011, 16:50     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #79
Цитата Сообщение от kravam Посмотреть сообщение
у условии есть противоречие:
Противоречия нет. Близкое к максимальному и максимальное - разные величины.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2011, 16:52     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,266
01.08.2011, 16:52  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику #80
ОК, может нет противоречия. Пусть нет. Нет нет и нет. Но:
"То есть представляем кратчайший путь, забраковываем потому что не максимален. Представляем любой другой путь, забраковываем что он не кратчайший.

Я в такие игры не играю. "
Yandex
Объявления
01.08.2011, 16:52     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Ответ Создать тему

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

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