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

Клетчатая доска - Определить количество способов добраться до последней клетки N-M - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Не работает функция sort (vector, vector) http://www.cyberforum.ru/cpp-beginners/thread1228298.html
#include <iostream> #include <conio.h> #include <vector> #include <string> #include <algorithm> using namespace std; class Name_pairs { private:
C++ Написать функцию вычисления произведения отрицательных чисел для трех целых аргументов Написать функцию вычисления произведения отрицательных чисел для трех целых аргументов. Написать операторы вызова функции, с помощью которых определяется и выводится на экран произведение отрицательных чисел для следующих входных данных: a) k, r, y; b) 3, -4, k. http://www.cyberforum.ru/cpp-beginners/thread1228284.html
C++ Равномерное дополнение строки пробелами
Всем доброго времени суток.Имеется задача: Дан текст из нескольких строк. Написать функцию, равномерно дополняющую строку пробелами до определенной длины и с ее помощью отформатировать этот текст. В программе должны быть функции - ввода текста (из нескольких строк); - вывода текста на экран; - форматирования строки текста в соответствии с заданием. Подскажите КАК следует понимать условие...
Указатели на функции (Прата) - не пойму, как это работает C++
Стивен Прата "Язык программирования C++. Лекции и упражнения" 7 глава, стр. 355, листинг 7.18. fun_ptr.cpp // fun_ptr.cpp -- pointers to functions #include <iostream> double betsy(int); double pam(int); // second argument is pointer to a type double function that
C++ Как ограничить поле ввода только одним символом? А двумя? http://www.cyberforum.ru/cpp-beginners/thread1228219.html
Как ограничить поле ввода только одним символом? А двумя? Например чтобы сразу после нажатия клавиши(двух), программа переходила к следующей операции, не ожидая нажатия "ентер", либо же не давала ввести символов больше положенного? Как сделать так, чтобы можно было напечатать в строку ввода только определённые символы, например y/n? Спасибо.
C++ Невозможно запустить программу. Отсутствует libiconv-2.dll Запуск программы невозможен так как на компьютере отсутствует libiconv-2.dll.попробуйте переустановить программу Добавлено через 36 секунд Что нужно сделать? подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2796 / 1572 / 246
Регистрация: 03.05.2010
Сообщений: 3,647
17.07.2014, 11:35     Клетчатая доска - Определить количество способов добраться до последней клетки N-M
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
/////////////////////////////////////////////////////////////////////////////////////////
//Задача такая: дана клетчатая доска NxM (1 <= N,M <= 1000), мы находимся в самой 
//первой клетке 1-1. Нужно определить количество способов добраться до последней клетки N-M. 
//Можно двигаться только вправо и вниз, также на доске существуют препятствия с известными 
//координатами, через них пройти нельзя. Входные данные (Пример):
//3 3 - размеры доски
//1 - кол-во преград
//2 2 - координаты преграды
//
//Так как в конце может получиться большое число, требуют в ответе написать остаток 
//от деления на 1 000 000 007.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <set>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::pair       < int,  int >   T_cell;
typedef std::set        < T_cell    >   T_cells;
typedef std::complex    < int       >   T_int_comlex;
typedef long                            T_paths_count;
typedef T_paths_count*                  T_row;
typedef T_row*                          T_matr;
/////////////////////////////////////////////////////////////////////////////////////////
T_paths_count   const   OBSTACLE_VAL        =   -1;
T_paths_count   const   MODULUS             =   1000000007;
T_paths_count   const   HALF_OF_MODULUS     =   MODULUS / 2;
/////////////////////////////////////////////////////////////////////////////////////////
T_cells     get_rand_obstacles
    (
        int     n,
        int     m
    )
{
    size_t      obstacles_count     =   rand() % ( n * m / 3 + 1 );
    T_cells     res_cells;
 
    while( res_cells.size() < obstacles_count )
    {
        res_cells.insert
            (
                T_cell
                    (
                        rand() % n,
                        rand() % m
                    )
            );
    }//while
 
    return  res_cells;
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_insert_obstacle_in_board
{
    //-----------------------------------------------------------------------------------
    T_matr  &   board_;
    //-----------------------------------------------------------------------------------
    T_insert_obstacle_in_board( T_matr  &   board )
        :
        board_( board )
    {}
    //-----------------------------------------------------------------------------------
    void    operator() ( T_cell     const   &   cell )
    {
        board_
            [ cell.first    ]
            [ cell.second   ]   =   OBSTACLE_VAL;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
void    fill_board_of_obstacles
    (
        T_matr              &   board,
        T_cells     const   &   obstacles
    )
{
    std::for_each
        (
            obstacles.begin             (),
            obstacles.end               (),
            T_insert_obstacle_in_board  ( board )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
inline  void    normalize( T_paths_count  &   val )
{
    if( val     >=  HALF_OF_MODULUS )
    {
        val     %=  MODULUS;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
T_paths_count   get_paths_count_congruent_modulo_in_board_with_sizes
    (
        int         modulus,
        T_matr  &   board,
        int         n,
        int         m
    )
{
    if  (
                board[0][0]             ==  OBSTACLE_VAL
            ||  board[n - 1][m - 1]     ==  OBSTACLE_VAL
        )
    {
        return  0;
    }
 
    for( int  i = 0; i < n; ++i )
    {
        for( int  j = 0; j < m; ++j )
        {
            T_paths_count     &   cur_cell_val_ref    =   board[i][j];
 
            if  (
                    cur_cell_val_ref    !=  OBSTACLE_VAL
                )
            {
                cur_cell_val_ref    =   0;
 
                if  (
                            i   ==  0
                        &&  j   ==  0
                    )
                {
                    cur_cell_val_ref    =   1;
                }
 
                if  (
                            j   >   0
                        &&  board[i][j - 1]     !=  OBSTACLE_VAL
                    )
                {
                    cur_cell_val_ref    +=  board[i][j - 1];
                    normalize( cur_cell_val_ref );
                }//if
 
                if  (
                            i   >   0
                        &&  board[i - 1][j]     !=  OBSTACLE_VAL
                    )
                {
                    cur_cell_val_ref    +=  board[i - 1][j];
                    normalize( cur_cell_val_ref );
                }//if
            }//if
        }//for
    }//for
 
    return  board[n - 1][m - 1];
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_print_cell
{
    void    operator()  ( T_cell    const   &   cell )
    {
        std::cout   <<  T_int_comlex
                            (
                                cell.first,
                                cell.second
                            )
 
                    <<  '\t';
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    srand(unsigned(time(0)));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите размеры доски:"
                    <<  std::endl
                    <<  "\tn = ";
 
        int     n   =   0;
        std::cin    >>  n;
        std::cout   <<  "\tm = ";
        int     m   =   0;
        std::cin    >>  m;
 
        T_matr  board   =   new     T_row[n];
 
        for( int  i = 0; i < n; ++i )
        {
            board[i]    =   new     T_paths_count[m]; 
        }
 
        T_cells     obstacles   =   get_rand_obstacles( n, m );
 
        fill_board_of_obstacles
            (
                board,
                obstacles
            );
 
        T_paths_count   paths_count_congruent_modulo
            =   get_paths_count_congruent_modulo_in_board_with_sizes
                    (
                        MODULUS,
                        board,
                        n,
                        m
                    );
 
        /*
        std::cout   <<  "Координаты препятствий:"
                    <<  std::endl;
 
        std::for_each
            (
                obstacles.begin     (),
                obstacles.end       (),
                T_print_cell        ()
            );
        */
 
        std::cout   <<  std::endl
                    <<  "Число препятствий\t: "
                    <<  obstacles.size()
                    <<  std::endl
                    <<  "Число путей по модулю\t: "
                    <<  paths_count_congruent_modulo
                    <<  std::endl;
    }
}
 
Текущее время: 01:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru