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

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

Восстановить пароль Регистрация
 
thejadefalcon
 Аватар для thejadefalcon
0 / 0 / 0
Регистрация: 23.09.2013
Сообщений: 41
16.07.2014, 20:58     Клетчатая доска - Определить количество способов добраться до последней клетки N-M #1
Привет. Задача такая: дана клетчатая доска 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++ Подсчитать количество способов замостить шахматную доску доминошками
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N C++
C++ Найти количество способов
Определить, являются ли клетки (a, b), (c, d) полями одного цвета на шахматной доске C++
Вычислить количество способов группировки K предметов из N при больших N C++
C++ Составить программу, которая, по данным N и K, вычисляет количество способов группировки K предметов из N
Определить количество способов укладки плиток на оставшиеся места C++
Определить цвет клетки шахматного поля C++
C++ Определить может ли конь попасть с первой клетки на вторую одним ходом?
Определить количество элементов массива, в которых сумма первой и последней цифр является четным числом C++
Сколько различных способов есть у зайца добраться до вершины лестницы? C++
Шахматная доска: определить являются ли поля (к, l) и (m, n) полями одного цвета C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
6055 / 5658 / 1828
Регистрация: 18.12.2011
Сообщений: 14,452
Завершенные тесты: 1
16.07.2014, 21:20     Клетчатая доска - Определить количество способов добраться до последней клетки N-M #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
 Аватар для thejadefalcon
0 / 0 / 0
Регистрация: 23.09.2013
Сообщений: 41
16.07.2014, 21:30  [ТС]     Клетчатая доска - Определить количество способов добраться до последней клетки N-M #3
Об этом речь в другой раз . Так как k может быть равно "0", этот массив даже не будет использоваться. Все же Ваш вариант взял.. Но..
Думаю, речь об огромных числах и типах.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.07.2014, 23:04     Клетчатая доска - Определить количество способов добраться до последней клетки N-M #4
thejadefalcon, я не разбирал код, но 1 баг точно вижу! ты все насчитываешь и только в конце берешь ответ для клетки по модулю, к этому времени количесво путей станет очень большим и переполнится. по модулю надо брать походу вычислений, т.е. для всех клеток надо брать колво путей в нее по модулю.
Mr.X
Эксперт С++
 Аватар для Mr.X
3011 / 1667 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
17.07.2014, 11:35     Клетчатая доска - Определить количество способов добраться до последней клетки N-M #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;
    }
}
Yandex
Объявления
17.07.2014, 11:35     Клетчатая доска - Определить количество способов добраться до последней клетки N-M
Ответ Создать тему
Опции темы

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