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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
#1

Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует - C++

23.08.2012, 10:31. Просмотров 1237. Ответов 15
Метки нет (Все метки)

Здравствуйте! Имеем функцию на C++.Помогите исправить ошибки, чтобы выводился правильный результат. Сначало условие, а ниже будет недоработанный код

Попытка к бегству
Узник пытается бежать из замка, который состоит из 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
10111
Выходные данные
impossible

Вот собственно сам код

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
#include <vcl.h>
#include <conio.h>
#include <iostream.h>
#pragma hdrstop
#pragma argsused
 
struct Node
{
   int x,y;
   Node *p;
};
 
Node* top=0;
 
Node* push(Node *top,const int xnew, const int ynew)
{
   Node* pv = new Node;
   pv->x=xnew;
   pv->y=ynew;
   pv->p=top;
   return pv;
}
 
Node* pop(Node*top,int&xcur,int & ycur)
{
   Node *pv=top->p;
   xcur=top->x;
   ycur=top->y;
   delete top;
   return pv;
}
 
int main()
{
   Randomize;
   int nstr,nstb,i,j,fstr,fstb,count,numturn;
   int flab(int x,int y,int **mass, const int nr,const int nc,int count,int numturn);
   cout<<"Enter size of massiv"<<endl;
   cin>>nstr>>nstb;
   
   cout<<"Enter first coordinate"<<endl;
   cin>>fstr>>fstb;
   
   int **M=new int *[nstr];
   
   for(i=0;i<nstr;i++)
      M[i]=new int[nstb];
 
   for(i=0;i<nstr;i++)
      for(j=0;j<nstb;j++)
      {
        if((rand()-rand())>0)
           M[i][j]=1;
        else
           M[i][j]=0;
     }
 
   for(i=0;i<nstr;i++)
   {
      for(j=0;j<nstb;j++)
         cout<<M[i][j]<<' ';
      cout<<endl;
   }
 
   count=0;
   numturn=0;
   M[fstr][fstb]=0;
   int pr=flab(fstr,fstb,M,nstr,nstb,count,numturn);
 
   cout<<endl<<endl;
 
   for(i=0;i<nstr;i++)
   {
      for(j=0;j<nstb;j++)
         cout<<M[i][j]<<' ';
      cout<<endl;
   }
 
   getch();
}
 
   int flab(int x,int y,int **mass, const int nr,const int nc,int count,int numturn)
   {
      int prom;
     
      if(mass[x][y]==0)
      {
         if(x==0||x==nr-1||y==0||y==nc-1)
         {
             cout<<"exit"<<endl;
             return(1);
         }
         else
        {
            mass[x][y]=2;
            count=0;
            numturn++;
            top=push(top,x,y);
         }
   }
   else
   {
      if(count==4)
      {
         if(numturn>0)
         {
            numturn--;
            top=pop(top,x,y);
           count=0;
         }
         else
         {
            cout<<"home"<<endl;
            return 0;
          }
      }
    }
 
   switch(count)
   {
      case 0: count++;
                 prom=flab(x,y-1,mass,nr,nc,count,numturn);
                 break;
 
      case 1: count++;
                 prom=flab(x,y+2,mass,nr,nc,count,numturn);
                 break;
 
     case 2: count++;
                prom=flab(x-1,y-1,mass,nr,nc,count,numturn);
                break;
 
     case 3: count++;
                prom=flab(x+2,y,mass,nr,nc,count,numturn);
                break;
   }
 }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2012, 10:31     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует
Посмотрите здесь:

найти количество различных маршрутов, ведущих к спасению C++
C++ Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
C++ Количество маршрутов с препятствиями
C++ Определить самое короткое слово предложения, первое, если таких несколько.
C++ Количество маршрутов
Вывести время отправления и номера маршрутов, проходящих через данный населенный пункт C++
C++ Выведение всех возможных маршрутов в неориентированном графе
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.08.2012, 10:53     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #2
Юлия17071992, Если прям для условия задачи, то можно так:
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
#include<iostream>
using namespace std;
int main()
{
    int N, M, i, j;
    scanf("%d %d", &N, &M); 
    int **a, **b;
    a=new int*[N]; b=new int*[N];
    for(i=0; i<N; i++)
    {
        a[i]=new int[M]; b[i]=new int[M];
        for(j=0; j<M; j++)
        {
            cin>>a[i][j]; b[i][j]=0;
        }
    }
    b[N-1][0]=1;
    for(i=1; i<M; i++)
        if(a[N-1][i]==1)
            b[N-1][i]=b[N-1][i-1];
        else
            b[N-1][i]=0;
    for(i=N-2; i>=0; i--)
        if(a[i][0]==1)
            b[i][0]=b[i+1][0];
        else
            b[i][0]=0;
    for(i=N-2; i>=0; i--)
        for(j=1; j<M; j++)
            if(a[i][j]==1)
                b[i][j]=b[i+1][j]+b[i][j-1];
            else
                b[i][j]=0;
    if(b[0][M-1])
        cout<<b[0][M-1]<<endl;  
    else
        cout<<"impossible"<<endl;
    return 0;
}
Кстати, по моему Вам давали похожий по функциональности код, а Вы его почему-то не взяли за основу. Если не секрет, где взяли код, который показываете в этой теме?
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
28.08.2012, 12:43  [ТС]     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #3
Код начинала писать с моим преподавателем по программированию, но мне был примерный планчик накидан, как он будет выглядеть. И вот что получилось видите сами

Добавлено через 1 минуту
То есть это и есть работающая программка?
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 12:51     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #4
Цитата Сообщение от Юлия17071992 Посмотреть сообщение
То есть это и есть работающая программка?
- да есть здесь 3-х мерный алгоритм Дейкстры так же есть доработка поиска в глубину для решения этой же задачи (верней более широкой - з-х мерного лабиринта), могу приаттачить экзешник...
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 13:12     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #5
Ниже аттачу поиск Дейкстры и поиск в глубину. Скрины отработки для решения именно этого лабиринта
3 5 1
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
На первом скрине отработка алгоритма который дал по ссылке, на последующих скриншоты отработки приложений из аттача этого поста.

Не по теме:

От себя добавлю : С преподавателем вы концептуально ошиблись при решении данной задачи. Мой совет - кардинально пересмотреть алгоритм поиска!

Миниатюры
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует   Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует   Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует  

Вложения
Тип файла: rar DeepthSearch.exe.rar (73.8 Кб, 5 просмотров)
Тип файла: rar DeikstraSearch.exe.rar (73.9 Кб, 5 просмотров)
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.08.2012, 13:15     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #6
Цитата Сообщение от Юлия17071992 Посмотреть сообщение
То есть это и есть работающая программка?
да, это и есть работающая программка

Добавлено через 1 минуту
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
От себя добавлю : С преподавателем вы концептуально оишблись при решении данной задачи. Мой совет - кардинально пересмотреть алгоритм поиска!
самый простой способ решения этой задачи: методом ДП (динамического программирования), проще ничего нет.
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 13:19     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
да, это и есть работающая программка
- Вы сами можете сказать логику какого из известных алгоритмов поиска он использует? И можно поросить вывести пути выхода в качестве числовых значений вершин?(думаю будете разочарованы ответами)

Не по теме:

Я ещё раз повторюсь - неверный у ТС алгоритм поиска, его просто нет, уже хотябы DFS из поиска в глубину применили



Добавлено через 1 минуту
Цитата Сообщение от valeriikozlov Посмотреть сообщение
(динамического программирования), проще ничего нет.
- можно получить ответ на этот вопрос
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
И можно поросить вывести пути выхода в качестве числовых значений вершин?
.

Не по теме:

Обещаю изменить своё мнение если выведите правильные маршруты на экран а не количество (но пока я вижу концептуальную дыру в алгоритме)

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.08.2012, 13:21     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #8
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- Вы сами можете сказать логику какого из известных алгоритмов поиска он использует?
используется метод ДП.

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
И можно поросить вывести пути выхода в качестве числовых значений вершин?
В этой задаче требуется:
Цитата Сообщение от Юлия17071992 Посмотреть сообщение
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.
Если нужно будет выводить пути выхода в качестве числовых значений вершин, то это будет совсем другая задача. )
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 13:24     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
сли нужно будет выводить пути выхода в качестве числовых значений вершин, то это будет совсем другая задача. )
- суть в том, что подсчитывать можно количество неверных путей, потому и прошу вывести их чтобы было видно какие пути просуммировали.

Не по теме:

valeriikozlov, задачу подсчёта можно реализовать рекурсивным проходом по всем вершинам, а вот прямой перебор как сейчас для меня весьма и весьма сомнителен

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.08.2012, 13:27     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #10
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- суть в том, что подсчитывать можно количество неверных путей, потому и прошу вывести их чтобы было видно какие пути просуммировали.
Зачем такие сложности? Методом ДП считаются только верные пути, за один проход по массиву.
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 14:02     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #11
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Зачем такие сложности? Методом ДП считаются только верные пути, за один проход по массиву.
valeriikozlov, хорошо перефразирую вопрос - сколько путей выводит ваш алгоритм для приведенного в задании лабиринта?И сколько по настоящему путей существует ?
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 14:05     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #12
PS:Это уже для ТС
Цитата Сообщение от Юлия17071992 Посмотреть сообщение
Входные данные
3 5
11111
10101
11111
Выходные данные
3
- не 3 а четыри!
Миниатюры
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует  
-=ЮрА=-
Заблокирован
Автор FAQ
28.08.2012, 14:09     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #13
Цитата Сообщение от Юлия17071992 Посмотреть сообщение
3 5
11101
10101
10111
Выходные данные
impossible
- ОМГ, см скриншот
Юля, где в комнате вход где выход?Это ведь концептуально важно описать точку входа и точку выхода, как вообще без этого можно решать указанную задачу
Миниатюры
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует  
-=ЮрА=-
28.08.2012, 14:12
  #14

Не по теме:

Юлия17071992, ещё раз призову к посту 5 - для данной задачи более всего подходит поиск в глубину, просто нужно не останавливать DFS как у меня при нахождении первого же пути к выходу, а прогнать алгоритм по всем вершинам и подсчитать число путей обеспечивающих выход...

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.08.2012, 15:42     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #15
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
valeriikozlov, хорошо перефразирую вопрос - сколько путей выводит ваш алгоритм для приведенного в задании лабиринта?И сколько по настоящему путей существует ?
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- не 3 а четыри!
нет, правильный ответ 3. Четвертый путь не удовлетворяет условию задачи:

Цитата Сообщение от Юлия17071992 Посмотреть сообщение
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.
Добавлено через 3 минуты
-=ЮрА=-, Кстати, Вы не правильно путь на тестовом поле изображаете:


Цитата Сообщение от Юлия17071992 Посмотреть сообщение
Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.08.2012, 16:04     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует
Еще ссылки по теме:

C++ Упорядочить номера маршрутов по возрастанию (структуры)
Вывести k-ю степень s, если она существует и слово undefined в противном случае. C++
C++ Вывести ближайшее к заданному числу N простое число; если таких числа два, то вывести меньшее
Поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл C++
C++ Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города

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

Или воспользуйтесь поиском по форуму:
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
30.08.2012, 16:04  [ТС]     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует #16
-=ЮрА=-, сможете ли вы мне полностью прислать код от программки, от которой вы делали скриншоты? а то с помощью этих файлов не могу понять как работает
Yandex
Объявления
30.08.2012, 16:04     Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует
Ответ Создать тему
Опции темы

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