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

Алгоритм Ли или Маршрутный алгоритм (пр0блема с кодом) - C++

Восстановить пароль Регистрация
 
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
28.10.2012, 22:07     Алгоритм Ли или Маршрутный алгоритм (пр0блема с кодом) #1
Есть задача, точнее лаба, можно уже впарить преподу, но лично для себя хочу исправить проблему. Надо использовать алгоритм написанный в заголовке темы. Написал код. Но в коде есть проблемы, сам код работает по простому нормально, но когда усложняю задачу, работает криво.
Проблемы :
Я думаю главная проблема кода заключается в методе find, то есть как то надо нормально поправить проверку границ и обхода по горизонталях и диагоналях.
1) Например когда в матрице в низу в коде она есть пропуск сделать сверху, а не на середине, то проблема с выходом за пределы массива, подскажите как исправить.
2) Проблема в том, что когда есть 1 клетка пустая по которой может пройти по диагонали или горизонтали, кароче когда есть нормальный пусть но он как то не в том месте сделан, код работает криво, хотя есть возможность пройти.
3) Как можно еще упросить код, что можно или лучше добавить к нему или удалить с точки зрения эффективности и простоты ???
КОД ПЕРЕПИСАН из JAVA на C++, тут чет не работает(передача параметров забыл как писать), уж больно давно писал на С++
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
#include <iostream>
#include <string>
#include <conio.h>
#include <stdio.h>
#include <fstream>
#include <math.h>
 
using namespace std;
 
 
void show(int matrix[7][7]);
void searchStartAndEnd(int matrix[7][7], int x1, int y1, int x2, int y2);
void find(int x1, int y1, int x2, int y2, int count, int matrix[7][7]);
 
int main()
{
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    int count = 0;
    int matrix[7][7] = 
        {
            {3, 3, 3, 3, 3, 3, 3},
            {3, 0, 0, 0, 0, 0, 3},
            {3, 0, 0, 3, 0, 0, 3},
            {3, 1, 0, 3, 0, 2, 3},
            {3, 0, 0, 3, 0, 0, 3},
            {3, 0, 0, 0, 0, 0, 3},
            {3, 3, 3, 3, 3, 3, 3},
        };
    
     
        show(matrix);
        searchStartAndEnd(matrix, x1, y1, x2, y2);
        cout << endl;
        cout << "START =  " << x1 << "\t" << y1 << endl;
        cout << "END   =  " << x2 << "\t" << y2 << endl;
        cout << endl;   
        find(x1, y1, x2, y2, count, matrix);
        cout << endl;
        show(matrix);
        cout << endl;
        if(matrix[x2][y2] == 5) cout <<"found"<< endl;
        else cout << "not found\n";
        cout << "program end\n";
        cout << endl;
    system("PAUSE");
    return 0;
}
 
void show(int matrix[7][7]) {
        for(int i = 0; i < 7; i++) {
            for(int j = 0; j < 7; j++)
                cout << matrix[i][j] << " ";
            cout << endl;
        }
    }
 
void searchStartAndEnd(int matrix[7][7], int x1, int y1, int x2, int y2) {
        for(int i = 0; i < 7; i++) {
            for(int j = 0; j < 7; j++)
                if(matrix[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }
                else if(matrix[i][j] == 2) {
                    x2 = i;
                    y2 = j;
                }
        }
    }
 
void find(int x1, int y1, int x2, int y2, int count, int matrix[7][7]) {
        if(x1 == x2 && y1 == y2) return;
        if(count > 7 * 7) return;
        int d = 100;    
        int a = x1, b = y1;
        if(d > (abs((x1-1)-x2) + abs((y1-1)-y2))) {
            if(matrix[x1-1][y1-1] == 3) d = 100;
            else {
            d = abs((x1-1)-x2) + abs((y1-1)-y2);
            a = x1-1; b = y1-1;
            }
        }
        
        if(d > (abs((x1-1)-x2) + abs((y1)-y2))) {
            if(matrix[x1-1][y1] == 3) d = 100;
            else {
            d = abs((x1-1)-x2) + abs((y1)-y2);
            a = x1-1; b = y1;
            }
        }
        
        if(d > (abs((x1-1)-x2) + abs((y1+1)-y2))) {
            if(matrix[x1-1][y1+1] == 3) d = 100;
            else {
            d = abs((x1-1)-x2) + abs((y1+1)-y2);
            a = x1-1; b = y1+1;
            }
        }
        
        if(d > (abs((x1)-x2) + abs((y1+1)-y2))) {
            if(matrix[x1][y1+1] == 3) d = 100;
            else {
            d = abs((x1)-x2) + abs((y1+1)-y2);
            a = x1; b = y1+1;
            }
        }
        
        if(d > (abs((x1+1)-x2) + abs((y1+1)-y2))) {
            if(matrix[x1+1][y1+1] == 3) d = 100;
            else {
            d = abs((x1+1)-x2) + abs((y1+1)-y2);
            a = x1+1; b = y1+1;
            }
        }
        
        if(d > (abs((x1+1)-x2) + abs((y1)-y2))) {
            if(matrix[x1+1][y1] == 3) d = 100;
            else {
            d = abs((x1+1)-x2) + abs((y1)-y2);
            a = x1+1; b = y1;
            }
        }
        
        if(d > (abs((x1+1)-x2) + abs((y1-1)-y2))) {
            if(matrix[x1+1][y1-1] == 3) d = 100;
            else {
            d = abs((x1+1)-x2) + abs((y1-1)-y2);
            a = x1+1; b = y1-1;
            }
        }
        
        if(d > (abs((x1)-x2) + abs((y1-1)-y2))) {
            if(matrix[x1][y1-1] == 3) d = 100;
            else {
            d = abs((x1)-x2) + abs((y1-1)-y2);
            a = x1; b = y1-1;
            }
        }
        
        //cout<<endl;;
        //show(matrix);
        matrix[a][b] = 5;
        count++;
        find(a, b, x2, y2, count, matrix);      
}
Например в такой матрице уже не находит конец
3 3 3 3 3 3 3
3 0 0 0 0 0 3
3 0 0 3 0 0 3
3 0 0 3 0 2 3
3 0 0 3 0 0 3
3 1 0 3 0 0 3
3 3 3 3 3 3 3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2012, 22:07     Алгоритм Ли или Маршрутный алгоритм (пр0блема с кодом)
Посмотрите здесь:

C++ Алгоритм LZ78 или трудности реализации
Волновой или А* или Алгоритм ЛИ C++
Поиск наименьших двух элементов массива или алгоритм Хаффмана C++
Составить алгоритм, заменяющий каждый символ текста его ASCII кодом C++
Алгоритм или-не C++
Построить алгоритм декодирования сообщений закодированных кодом простым повторением C++
Составить алгоритм шифровальщик, который заменяет каждый символ текста его ASCII-кодом C++
Алгоритм Брона-Кербоша или поиск клик в графе C++

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

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

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