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

Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего - C++

Восстановить пароль Регистрация
 
spirart
2 / 2 / 3
Регистрация: 05.12.2011
Сообщений: 51
Завершенные тесты: 1
05.08.2014, 11:04     Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего #1
Всем привет!
Решаю вот такую простую задачку:

Игровое поле N x M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.
Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего.

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

Входной файл INPUT.TXT содержит в первой строке размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). В последующих N строках входного файла, каждая из которых описывает отдельную строку игрового поля, записаны через пробел по M целых чисел – длины шагов из клеток данной строки.

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

Выходной файл OUTPUT.TXT должен содержать одно число - число различных вариантов путей от верхнего левого угла до правого нижнего. Для каждого поля будет менее чем 231 различных путей.
Ссылка на нее: Задача


Вот мой код:

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
int main()
{
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    
    int  n, m;
    scanf("%d %d", &n, &m);
    int** a = new int*[n];
    int** l = new int*[n];
    for (int i = 0; i < n; i++) {
        l[i] = new int[m];
        a[i] = new int[m];
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
            l[i][j] = 0;
        }
    }
 
    l[0][0] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int pos = a[i][j];
 
            if (j+pos < m)
                l[i][j+pos] = l[i][j] + l[i][j+pos];
            if (i+pos < n)
                l[i+pos][j] = l[i][j] + l[i+pos][j];
        }
    }
    printf("%d", l[n-1][m-1]);
    return 0;
}
Моя программа выдает неверный результат, а я не понимаю, почему.
Помогите, пожалуйста, найти ошибку в коде.
Спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.08.2014, 11:04     Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего
Посмотрите здесь:

Заполнить матрицу, от левого верхнего угла по диагонали: вправо - вверх C++
C++ Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх.
Заполнение матрицы с левого нижнего угла по диагонали (исправить программу) C++
C++ Заполнить матрицу ЛП, от правого верхнего угла по диагонали: влево - вниз
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) C++
C++ Заполнить квадратную матрицу от левого верхнего угла по спирали
C++ Заполнить матрицу ЛП, от левого верхнего угла по диагонали: вправо - вверх
C++ Прокрутить четверти матрицы по часовой стрелке, начиная с верхнего левого угла

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
05.08.2014, 16:51     Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
/////////////////////////////////////////////////////////////////////////////////////////
//Игровое поле N x M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. 
//Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла 
//до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть 
//из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо 
//шага игрок покидает пределы поля, такой шаг запрещается.
//Требуется написать программу, которая определит число различных вариантов путей от верхнего 
//левого угла до правого нижнего.
//
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит в первой строке размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). 
//В последующих N строках входного файла, каждая из которых описывает отдельную строку игрового 
//поля, записаны через пробел по M целых чисел – длины шагов из клеток данной строки.
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//Выходной файл OUTPUT.TXT должен содержать одно число - число различных вариантов путей 
//от верхнего левого угла до правого нижнего. Для каждого поля будет менее чем 231 различных путей.
/////////////////////////////////////////////////////////////////////////////////////////
#include <fstream>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
const   int     ROWS_TOTAL_MAX  =   70;
const   int     COLS_TOTAL_MAX  =   ROWS_TOTAL_MAX;
/////////////////////////////////////////////////////////////////////////////////////////
int     field               [ ROWS_TOTAL_MAX ][ COLS_TOTAL_MAX ]   =   {0};
int     variants_counter    [ ROWS_TOTAL_MAX ][ COLS_TOTAL_MAX ]   =   {0};
/////////////////////////////////////////////////////////////////////////////////////////
bool    may_go_to_right
    (
        int     steps_count,
        int     cols_total,
        int     col
    )
{
    return  col + steps_count < cols_total;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    may_go_to_down
    (
        int     steps_count,
        int     rows_total,
        int     row
    )
{
    return  row + steps_count < rows_total;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     get_variants_count
    (
        int     rows_total,
        int     cols_total
    )
{
    for( int  i = 0; i < rows_total; ++i )
    {
        for( int  j = 0; j < cols_total; ++j )
        {
            int     variants_count  =       i == 0
                                        &&  j == 0
                                            ?   1
                                            :   variants_counter[i][j];
 
            int     steps_count     =   field[i][j];
 
            if  (
                        steps_count     ==  0
                    ||  variants_count  ==  0
                )
            {
                continue;
            }
 
            if  (
                    may_go_to_right
                        (
                            steps_count,
                            cols_total,
                            j
                        )
                )
            {
                variants_counter[i][ j + steps_count ]  +=  variants_count;
            }
 
            if  (
                    may_go_to_down
                        (
                            steps_count,
                            rows_total,
                            i
                        )
                )
            {
                variants_counter[ i + steps_count ][j]  +=  variants_count;
            }
        }//for
    }//for
 
    return  variants_counter[ rows_total - 1 ][ cols_total - 1 ];
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::ifstream   ifile("INPUT.TXT");
    int     rows_total  =   0;
    ifile   >>  rows_total;
 
    int     cols_total  =   0;
    ifile   >>  cols_total;
 
    for( int  i = 0; i < rows_total; ++i )
    {
        for( int  j = 0; j < cols_total; ++j )
        {
            ifile   >>  field[i][j];
        }//for
    }//for
 
    std::ofstream   ofile( "OUTPUT.TXT" );
 
    ofile   <<  get_variants_count
                    (
                        rows_total,
                        cols_total
                    );
}
Yandex
Объявления
05.08.2014, 16:51     Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего
Ответ Создать тему
Опции темы

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