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

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

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

Работа с графом - C++

13.04.2014, 13:30. Просмотров 140. Ответов 0
Метки нет (Все метки)

Смысл такой. Вводим поле n*m, вводим препятствие. (пустые клетки обозначены - 1, препятствия - 0). Строим матрицу смежности размером nk= n*m, анализируем поле (каждую клетку со смежными клетками по 4-м направлениям). куда можно сходить должны записать - 1, куда нельзя - 0. О своих косяках догадываюсь но исправить не могу, в общем помогите довести до рабочего состояния. заранее спасибо, эта работа для меня очень нужна, первый мой большой проект.

пример:
поле 2*2: (препятствие одно, координаты - 1,1, размеры - 1,1)
11
10
должна получиться матрица смежности:
0110
1000
1000
0000

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
#include "stdafx.h"
#include <iostream>
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
 
    int n, m, x, y, k, l, nkol;
    cout<<"Введите количество строк: ";
    cin>>n;
    cout<<"Введите количество столбцов: ";
    cin>>m;
 
    //создание массива, заполнение 1-ми
 
    int** a = new int* [n];
    for(int i=0; i<n; i++)
    {
        a[i] = new int[m];
        for(int j=0; j<m; j++)
        {
            a[i][j]=1;
        }
    }
 
    // вывод массива
 
    for(int i = 0; i < n; i++)
    {
        cout<<endl;
        for(int j = 0; j < m; j++)
        {            
            cout<<a[i][j]<<" ";
        }
    }
    cout<<endl;
    cout<<endl;
 
    //ввод препятствий, коррекция массива
 
    cout<<"Ввод препятствий (координаты x и y задают левый верхний угол препятствия):"<<endl;
    cout<<endl;
 
 
    cout<<"Введите количество препятствий: ";
    cin>>nkol;
 
    for (int g=1; g<=nkol; g++)
    {
        cout<<"Введите x"<<g<<": ";
        cin>>x;
        cout<<"Введите y"<<g<<": ";
        cin>>y;
        cout<<"Введите длину препятствия: ";
        cin>>k;
        cout<<"Введите ширину препятствия: ";
        cin>>l;
 
        for(int i=x; i<x+l; i++)
        {
            for(int j=y; j<y+k; j++)
            {
                a[i][j]=0;
            }
        }
        x=0;
        y=0;
        k=0;
        l=0;
    }
 
    // вывод скорректированного массива
 
    for(int i = 0; i < n; i++)
    {
        cout<<endl;
        for(int j = 0; j < m; j++)
        {            
            cout<<a[i][j]<<" ";
        }
    }
    cout<<endl;
 
    //создание матрицы смежности, массив b
 
    int nk;
    nk=n*m;
 
    int** b = new int* [nk];
    for(int q=0; q<nk; q++)
    {
        b[q] = new int[nk];
        for(int p=0; p<nk; p++)
        {
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<n; j++)
                {
                    if (a[i][j]==1 && a[i][j+1]==1) // проверка вправо
                    {
                        b[q][p]=1;
                    }
                    else b[q][p]=0;
                    if (a[i][j]==1 && a[i][j-1]==1) // проверка влево
                    {
                        b[q][p]=1;
                    }
                    else b[q][p]=0;
                    if (a[i][j]==1 && a[i+1][j]==1) // проверка вниз
                    {
                        b[q][p]=1;
                    }
                    else b[q][p]=0;
                    if (a[i][j]==1 && a[i-1][j]==1) // проверка вверх
                    {
                        b[q][p]=1;
                    }
                    else b[q][p]=0;
                }
            }
        }
    }
 
    // вывод массива b
 
    for(int q = 0; q < nk; q++)
    {
        cout<<endl;
        for(int p = 0; p < nk; p++)
        {            
            cout<<b[q][p]<<" ";
        }
    }
 
    cout<<endl;
    cout<<endl;
    system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2014, 13:30     Работа с графом
Посмотрите здесь:

Работа с Ориентированным графом - C++
Дан орграф. После удаления произвольных вершин может произойти всё что угодно, вопрос таков: Для каждого компонета связности выделить...

Работа с графом (Требуется по заявке клиента предложить способы обмена жилплощади) - C++
В файле записаны предложения по обмену жилплощадью. Имеются варианты размена одной квартиры на две других либо на квартиру и комнату....

Задание графом - C++
Задан граф, вывести все пары вершин, между которыми нет пути. можете помочь???

написать прогу с графом - C++
По таблице рёбер построить списки инцидентности ориентированного графа, удалить из графа вершины с номерами n1 и n2. Таблицу создать...

написать программу с графом - C++
В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько ...

Работа с графом - Matlab
Здравствуйте, у меня такая проблема ,по матрице смежности (7x7) со случайными числами я получил граф в котором присутствуют треугольники,...

Работа с графом - C#
Написать программу, которая находит по заданным вершинам графа все пути между ними и определяет кратчайший путь. Сам граф представлен в...

Работа с неориентированным графом - C#
Есть неориентированный граф 4х4, нужно составить алгоритм, который бы находил пути в которых принимают участие все элементы графа. Граф...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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