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

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

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

Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город - C++

13.06.2014, 22:13. Просмотров 371. Ответов 1
Метки нет (Все метки)

По системе двусторонних дорог, определить можно ли закрыв какие-либо 3 из них, добиться того, чтобы из города А нельзя было попасть в город Б.

вот собственно код

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
#include "stdafx.h"
#include <iostream>
using namespace std;
 
struct stack
{
 int datax;
 int datay;
 stack *next;
};
 
const int n = 6;
int i,j;
int matrix[n][n]= 
{
 {1,1,0,0,1,0},
 {1,1,1,0,1,0},
 {0,1,1,1,1,0},
 {0,0,1,1,1,1},
 {1,1,1,1,1,0},
 {0,0,0,1,0,1}
};
 
 
 
/*=====================PROTORYPE======================*/
void Push(stack *&top, int valuex, int valuey); //добавление в стек пути
stack *Delete(stack *&top); //удаление из стека
void Show(stack *top); //показать стек
stack *Search(stack *&top, int xf, int yf, int **&matrix, int **&visited, int n); //поиск пути
bool Elemente(stack *top, int i, int j); //проверка стека на наличие элемента
/*=====================BODY==========================*/
void main()
{
    setlocale (LC_ALL, "Rus");
    bool flag = false;
    int x, y;
 
    int **visited= new int *[n];
        for (i=0; i<n; i++)
            visited[i]=new int [n];
 
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            visited[i][j]=0;
 
    int **matrfunc= new int *[n];
        for (i=0; i<n; i++)
            matrfunc[i]=new int [n];
 
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            matrfunc[i][j]=matrix[i][j];
 
    for(i=0; i<n; i++)
    {
        cout<<"\n";
        for(j=0; j<n; j++)
        cout<<" "<<matrfunc[i][j]<<" ";
    }
 
 
    for(int k=0; k<3; k++)
    { 
    
    flag=false;
    
    while(!flag)
    {
    cout<<"\n enter the first coordinate path:";
    cin >> x;
    cout<<"\n enter the second coordinate path:";
    cin >> y;
    if ((x<0 || x>6) || (y<0 || y>6))
    {
        cout<<"\n The data is incorrect, please try again.";
        flag = false;
    }   
    else 
        {
        cout<< "\n The data is correct.";
        matrfunc[x][y]=0;
        matrfunc[y][x]=0;
        flag= true;
        }
        }
    }
    
    for(i=0; i<n; i++)
    {
        cout<<"\n";
        for(j=0; j<n; j++)
        cout<<" "<<matrfunc[i][j]<<" ";
    }
 
    int start,  finish, xs, ys, xf, yf;
    flag=false;
    do
    {
        cout <<"\n Enter begin path:";
        cin>>start;
        cout <<"\n Enter begin path:";
        cin>>finish;
 
        if (start<1 || start>6 || finish<1 || finish>6)
            {
            cout<<"\n The data is incorrect, please try again.";
            flag = false;
            }
        else
            {
                xs=start-1;
                ys=start-1;
                xf=finish-1;
                yf=finish-1;
                cout<<"\n The data is correct.";
                flag = true;
            }
    }
    while(!flag);
 
    stack * top=new stack;
    top->datax =xs;
    top->datay=ys;
    top->next=NULL;
 
    top = Search(top, xf, yf, matrfunc, visited, n);
 
    if(top!=NULL)
    Show(top);
    else 
    cout<<"\n no path";
 
    
 
    system("pause");
}
 
/*=====================FUNCTION======================*/
 
void push(stack *&top, int valuex, int valuey)
{
    stack* n = new stack;
    n -> datax = valuex;
    n -> datay = valuey;
    n -> next = top;
    top = n;
}
 
stack *Delete(stack *&top)
{
    stack *n = top->next;
    delete top;
    return n;
}
 
stack *Search(stack *&top, int xf, int yf, int **&matrix, int **&visited, int n)
{
    int i=0, j;
    bool flag=false;
    if(top->datax==xf && top->datay==yf)
        return top; 
    else 
    {
        j=top->datax;
        while(i<n || flag)
        {
 
            if(matrix[i][j]==1 && visited[i][j]==0 && Elemente(top,i,j)==false)
            {
                push(top, i, j);
                if(top->datax==xf && top->datay==yf)
                flag=true;
                else
                top=Search(top, xf,yf,matrix, visited, n);
            }
 
            else 
                i++;
        }
 
        if(flag==false)
        {
            visited[top->datax][top->datay]=1;
            top=Delete(top);
        }
        else 
            return top;
    }
 
}
 
void Show(stack *top)
{
    while(top!=NULL)
    {
        cout<<top->datax;
        cout<<" ,"<<top->datay<<"\n";
        top=top->next;
    }
}
 
bool Elemente(stack *top, int a, int b)
{
    bool flag=false;
    while(top!=NULL && !flag)
    {
        if(top->datax==a && top->datay==b)
        {
            flag = true;
        }
        top=top->next;
    }
        if (flag==true)
            return 1;
        else 
            return 0;   
}
при любых корректных данных выбивает следующее:
"Первый этап обработки исключения по адресу 0x011835CD в Laba1.exe: 0xC0000005: нарушение прав доступа при чтении по адресу 0xFDFDFE09."
подскажи в чем причина

(вначале вводим между какими городами хотим удалить дороги (3шт), затем из какого города в какой хотим попасть)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2014, 22:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город (C++):

По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B - C++
Подкиньте пожалуйста идей как решать

Какие SQL запросы нужны для того, чтобы можно было отображать материал базы данных в комбоксе. - C++
Помогите пожалуйста, какие SQL запросы нужны для того чтобы можно было отображать материал базы данных в комбоксе. если можно сделайте...

Определить есть ли в системе дорог город, куда можно попасть из любого другого, проезжая не более 100км - C++
Всем привет.Помогите с программой: Задана система односторонних дорог. Определить, есть ли в ней город, куда можно попасть из любого...

Где должны находиться текстовые файлы, для того чтобы с ними можно было работать? - C++
подскажите пожалуйста,где должны находиться текстовые файлы, для того чтобы с ними можно было работать? #include &quot;stdafx.h&quot; #include...

Определить, есть ли город, куда можно попасть из любого другого города, проезжая не более 100 км - Turbo Pascal
Всем привет.Помогите с программой: Задана система односторонних дорог. Определить, есть ли в ней город, куда можно попасть из любого...

По заданной системе односторонних дорог определить, есть ли город, куда можно попасть из любого другого - C (СИ)
Доброго времени суток! Такая задача: По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Skycat36
0 / 0 / 0
Регистрация: 23.04.2017
Сообщений: 2
23.04.2017, 12:25 #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
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
#include <iostream>
 
using namespace std;
 
class Roads {
 
    bool** visited;
 
    int count_roads(bool** a, int n, bool** visited, int current, int end, int S = 0) {
        if (current == end) {
            return ++S;
        }
        for (int i = 0; i < n; i++) {
            if (i != current && visited[current][i] != 1 && a[current][i] == 1) {
                visited[i][current] = 1;
                visited[current][i] = 1;
                S += count_roads(a, n, visited, i, end);
                visited[current][i] = 0;
                visited[i][current] = 0;
            }
        }
        return S;
    }
 
 
public:
 
    void init(int n, bool** a) {
        visited = new bool *[n];
        for (int i = 0; i < n; i++) {
            visited[i] = new bool[n];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = 0;
            }
        }
    }
 
    void output(int n, bool** a) {
        for (int i = 1; i <= 2 * n; i++) {
            if (i % n == 1) {
                cout << "    ";
                if (i <= n) {
                    cout << i;
                }
                else {
                    cout << "-";
                }
            }
            else {
                if (i <= n) {
                    cout << "  " << i;
                    if (i == n) {
                        cout << endl;
                    }
                }
                else {
                    cout << "---";
                }
            }
        }
        cout << endl;
 
        for (int i = 0; i < n; i++) {
            cout << i + 1 << "|  ";
            for (int j = 0; j < n; j++) {
                cout << a[i][j] << "  ";
            }
            if (i + 1 == n) {
                cout << endl;
            }
            else {
                cout << endl << " |" << endl;
            }
        }
        cout << endl;
    }
 
    void input(int n, bool** a, int &start, int &end) {
        char c = ' ';
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                while (c != 'Y' && c != 'N') {
                    cout << "Is there a road between cities " << i + 1 << " and " << j + 1 << "? (Y/N): ";
                    cin >> c;
                    if (c != 'Y' && c != 'N') {
                        cout << "Wrong! Try again!" << endl;
                    }
                }
                if (c == 'Y') {
                    a[i][j] = 1;
                    a[j][i] = 1;
                }
                else {
                    a[i][j] = 0;
                    a[j][i] = 0;
                }
                c = ' ';
            }
        }
        for (int i = 0; i < n; a[i][i] = 0, i++);
        cout << endl;
 
        output(n, a);
 
        while (start < 1 || start > n) {
            cout << "Enter the number of the initial city: ";
            cin >> start;
            if (start < 1 || start > n) {
                cout << "Wrong! Try again!" << endl;
            }
        }
        while (end < 1 || end > n) {
            cout << "Enter the number of the final city: ";
            cin >> end;
            if (end < 1 || end > n) {
                cout << "Wrong! Try again!" << endl;
            }
        }
        cout << endl;
 
    }
 
    int count_roads(bool** a, int n, int start, int end) {
        start -= 1;
        end -= 1;
        return count_roads(a, n, visited, start, end);
    }
 
    bool is_possible(int n, bool** a, int start, int end) {
        int start_roads = 0, end_roads = 0;
        for (int i = 0; i < n; i++) {
            start_roads += a[i][start - 1];
            end_roads += a[i][end - 1];
        }
        return (start_roads <= 3 || end_roads <= 3 || count_roads(a, n, start, end) <= 3);
    }
 
};
 
int main() {
 
    Roads obj;
 
    int n = 0;
    while (n < 3) {
        cout << "Enter the number of cities: ";
        cin >> n;
        if (n < 3) {
            cout << "Wrong! Try again!" << endl;
        }
    }
    cout << endl;
    bool** a = new bool *[n];
    for (int i = 0; i < n; i++) {
        a[i] = new bool [n];
    }
 
    int start = 0, end = 0;
    obj.input(n, a, start, end);
    
    obj.init(n, a);
    
    if (obj.is_possible(n, a, start, end)) {
        cout << "YES! If you close any 3 roads, you won't be able to get from city " << start << " to city " << end << endl;
    }
    else {
        cout << "NO! If you close any 3 roads, you will be able to get from city " << start << " to city " << end << endl;
    }
    
    system("pause");
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2017, 12:25
Привет! Вот еще темы с ответами:

Графы: определить, есть ли город, куда можно попасть из любого другого города, проезжая не более 100 км - Delphi
Всем привет.Помогите с программой: Задана система односторонних дорог. Определить, есть ли в ней город, куда можно попасть из любого...

Определить, можно ли попасть по дорогам из l-того пункта в m-ый - VBA
Имеется n населенных пунктов, пронумерованных от 1 до n (n=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть...

Определить, можно ли попасть по этим дорогам из l-того пункта в m-ый - VBA
1. Имеется n населенных пунктов, пронумерованных от 1 до n (n=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли...

Где можно взять ftp-компонент, для того чтобы можно было закачивать со своего скрипта на фтп-сервак файлы? - C# ASP.NET
Народ подскажите где можно взять ftp-компонент, для того чтобы можно было закачивать со своего скрипта на фтп-сервак файлы.


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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