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

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

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

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

13.06.2014, 22:13. Просмотров 307. Ответов 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шт), затем из какого города в какой хотим попасть)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2014, 22:13     Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город
Посмотрите здесь:

C++ Какие книжки посоветуете почитать о С, чтобы было понятно новичку?
Путем перестановки квадратной веществ. матрицы добиться того, чтобы максимум находился в левом верхнем углу C++
C++ Путем перестановки элементов квадратной матрицы добиться того,чтобы ее макс элемент находился в левом верхнем углу
C++ По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B
Задана вещественная матрица размером m×n. Найти наибольший элемент. Перестановкой строк и столбцов, добиться того, чтобы данный элемент оказался в вер C++
Какие SQL запросы нужны для того, чтобы можно было отображать материал базы данных в комбоксе. C++
C++ Добиться того, чтобы наибольший элемент данной матрицы оказался в верхнем левом углу
C++ Дана (построчно) вещественная матрица размером МхН. Переставляя ее строки и столбцы, добиться того, чтобы наибольший
Переставляя строки и столбцы, добиться того, чтобы наибольший элемент матрицы оказался в правом нижнем углу C++
C++ Где должны находиться текстовые файлы, для того чтобы с ними можно было работать?
Определить есть ли в системе дорог город, куда можно попасть из любого другого, проезжая не более 100км C++
C++ Определить, можно ли попасть по дорогам из первого населенного пункта в последний

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Skycat36
0 / 0 / 0
Регистрация: 23.04.2017
Сообщений: 1
23.04.2017, 12:25     Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город #2
#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;
}
Yandex
Объявления
23.04.2017, 12:25     Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город
Ответ Создать тему
Опции темы

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