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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
thejadefalcon
0 / 0 / 0
Регистрация: 23.09.2013
Сообщений: 41
#1

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

16.07.2014, 20:58. Просмотров 550. Ответов 4
Метки нет (Все метки)

Привет. Задача такая: дана клетчатая доска NxM (-1000 <= N,M <= 1000), мы находимся в самой первой клетке 1-1. Нужно определить количество способов добраться до последней клетки N-M. Можно двигаться только вправо и вниз, также на доске существуют препятствия с известными координатами, через них пройти нельзя. Входные данные (Пример):
3 3 - размеры доски
1 - кол-во преград
2 2 - координаты преграды

Так как в конце может получиться большое число, требуют в ответе написать остаток от деления на 1000000007.

В общем-то я сделал: http://ideone.com/3N8Nsk

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
#include <iostream>
 
using namespace std;
 
bool barrier(int i, int j, int **Arr, int n) { // Функция проверяет преграда ячейка или нет
    for (int k = 0; k < n; k++) {
        if (i == Arr[k][0]-1 && j == Arr[k][1]-1) {
            return true;
        }
    }
    return false;
}
 
int main() {
    int n,m,k;
    int row = 0;
    int col = 0;
    cin >> n >> m; // Размер клеточной доски
        
    unsigned long **possible = new unsigned long* [n]; 
    for (int i = 0; i < n; i++)
        possible[i] = new unsigned long [m]; 
 
    cin >> k; // Количество преград
 
    int **Arr = new int* [2]; 
    for (int i = 0; i < k; i++)
        Arr[i] = new int [2]; 
 
    if (k > 0) {
        for (int i = 0; i < k; i++) { // Заносим координаты преград
            for (int j = 0; j < 2; j++) {
                cin >> Arr[i][j];
            }
        }
    }
    
    possible[row][col] = 1;
    bool start = false;
 
    for (int i = 0; i < n; i++) { // Считаем для каждой ячейки - сколькими способами можно до нее добраться
        for (int j = 0; j < m; j++) {
            if (barrier(i, j, Arr, k)) { // Если ячейка преграда, делаем кол-во способов добраться до нее 0, чтобы дальнейшие ячейки не могли иметь путь через нее
                possible[i][j] = 0;
                continue;
            }
            if (start) {
                if (i == 0) {
                    possible[i][j] = possible[i][j-1]; // Если ячейки из верхней строчки, то можем попасть в нее только с левой ячейки, получаем из нее коли-чество способов добраться
                    continue;
                }
                if (j == 0) { // Если ячейка из левого столбика, то можем попасть в нее только сверху, получаем из нее коли-чество способов добраться
                    possible[i][j] = possible[i-1][j];
                    continue;
                }
                possible[i][j] = possible[i][j-1] + possible[i-1][j]; // В иных случаях прибавляем кол-во способов добраться из верхней ячейки и левой
            }
            else {
                start = true;
            }
        }
    }
 
    cout << possible[n-1][m-1]%1000000007; // Выводим остаток от деления на 1000000007
    
    return 0;
}
Для простых тестовых примеров работает, а вот для БОЛЬШИХ тестовых примеров 1000х1000, например, думаю, что работает неправильно. Потому что в компиляторе на компьютере ответ один, на онлайн компиляторе ответ другой. Думаю, что неправильные типы у меня. Помогите.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2014, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Клетчатая доска - Определить количество способов добраться до последней клетки N-M (C++):

Сколько различных способов есть у зайца добраться до вершины лестницы? - C++
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке...

Определить количество способов укладки плиток на оставшиеся места - C++
Задача G. Укладка плитки (Время: 1 сек. Память: 16 Мб Баллы: 100) В процессе ремонта в Лаборатории Информационных Технологий строителям...

Определить количество символов между первой и последней двоеточиями строки - C++
Определить количество символов между первой и последней двоеточиями строки.

Требуется определить количество способов выплаты n рублей монетами по 1, 2, 5 и 10 рублей - C++
Формат входных данных На вход программе дается одно натуральное число n (n ≤ 99). Формат выходных данных Требуется вывести одно...

Определить количество элементов массива, в которых сумма первой и последней цифр является четным числом - C++
дан массив a(n). определить количество элементов массива , в которых сумма первой и последней цифр является четным числом

Найти количество способов, которыми фишка может дойти до последней клетки - Free Pascal
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти количество способов, которыми фишка может дойти до...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zss
Модератор
Эксперт С++
6366 / 5930 / 1923
Регистрация: 18.12.2011
Сообщений: 15,239
Завершенные тесты: 1
16.07.2014, 21:20 #2
Цитата Сообщение от thejadefalcon Посмотреть сообщение
int **Arr = new int* [2];
for (int i = 0; i < k; i++) Arr[i] = new int [2];
Создали указатели на 2 строки, а заполняете k.
C++
1
2
3
if(k<=0)return 0;
int **Arr = new int* [k];
 for (int i = 0; i < k; i++) Arr[i] = new int [2];
thejadefalcon
0 / 0 / 0
Регистрация: 23.09.2013
Сообщений: 41
16.07.2014, 21:30  [ТС] #3
Об этом речь в другой раз . Так как k может быть равно "0", этот массив даже не будет использоваться. Все же Ваш вариант взял.. Но..
Думаю, речь об огромных числах и типах.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.07.2014, 23:04 #4
thejadefalcon, я не разбирал код, но 1 баг точно вижу! ты все насчитываешь и только в конце берешь ответ для клетки по модулю, к этому времени количесво путей станет очень большим и переполнится. по модулю надо брать походу вычислений, т.е. для всех клеток надо брать колво путей в нее по модулю.
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
17.07.2014, 11:35 #5
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;
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2014, 11:35
Привет! Вот еще темы с ответами:

Посчитать количество различных комбинаций прыжков, которые помогут добраться из нулевой клетки в клетку n - Delphi
Задание: Кузнечик прыгает по клеточкам тетрадного листа, за один прыжок он перепрыгивает от L до R клеток. Посчитать количество различных...

Cколько различных способов есть у зайца добраться до вершины лестницы - C#
1. В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его...

Шахматная доска, расстояние от начальной до заданной точки, некоторые клетки заняты фигурами - Pascal
На шахватной доске (не обязательно 8х8) стоит ферзь. Нужно определить, за сколько ходов он может добраться в заданную точку, если известны...

сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N - Delphi
Доброго времени суток, уважаемые форумчане! Есть задача: В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.07.2014, 11:35
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru