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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
vikichocolate
 Аватар для vikichocolate
25 / 14 / 1
Регистрация: 11.11.2011
Сообщений: 94
#1

Задача про минимальный путь в лабиринте. - C++

25.11.2011, 19:03. Просмотров 1976. Ответов 7
Метки нет (Все метки)

Вот собственно сама задача:


Разработать программу, которая ищет минимальный путь в лабиринте. Лабиринт представляет собой матрицу 10х10. Клетки, по которым можно передвигаться, заполнены единицами. Клетки, через которые проходить нельзя, заполнены нулями. Необходимо найти кратчайший путь из верхней левой в правую нижнюю клетку.


И мой код. Но некоторые тесты он не проходит. Нужно помочь добить ее до 100%. Очень прошу помочь, т.к. в универе никто толком нормально помочь не может(вернее не хочет)...

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
#include<iostream>
#include<fstream>
using namespace std;
 
void main()
{
    int x, y ;  // размеры матрицы
    ifstream in;
    in.open("input.txt");
    ofstream  out;
    out.open("output.txt"); 
    in>>x>>y;
    int **b=new int*[x];
    for(int i=0; i<x; i++)   
        b[i] = new int[y];
    int **a=new int*[x];
    for (int i=0;i<x;i++)
    {
        a[i]=new int[y];
        for (int j=0;j<y;j++)
            in>>a[i][j];
    } 
    in.close();
    if(a[0][0]==0 && a[x-1][y-1]==0)
    {
        out<<"wrong matrix!"<<endl; 
    }
 
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            b[i][j]=0;
        }
    }
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            if(a[i][j]==0)
                a[i][j]=2;
            else
                a[i][j]=1;
        }
    }
 
 
 
    int k=1;
    //b[0][0]=k;
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            if (i!=0 && j!=0) {
                k=a[i][j]+min(b[i-1][j], b[i][j-1]);
                b[i][j]=k+1;
                k++; 
            } 
        }
    }
    out<<b[x-1][y-1]; 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vikichocolate
 Аватар для vikichocolate
25 / 14 / 1
Регистрация: 11.11.2011
Сообщений: 94
20.12.2011, 01:13  [ТС]     Задача про минимальный путь в лабиринте. #2
A2 Разработать программу, которая ищет минимальный путь в лабиринте. Лабиринт представляет собой матрицу 10х10. Клетки, по которым можно передвигаться, заполнены единицами. Клетки, через которые проходить нельзя, заполнены нулями. Необходимо найти кратчайший путь из верхней левой в правую нижнюю клетку.




Учитель сказал, что это неправильное решение...Хотя вроди норм работает.
Гляньте, пжл!!!!!Горит очень сильно!!!!Умоляю!!!!!!Подправьте код!!!!!!




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
#include<iostream>
#include<fstream>
using namespace std;
 
void main()
{
    int x, y ;  // размеры матрицы
    ifstream in;
    in.open("input.txt");
    ofstream  out;
    out.open("output.txt"); 
    in>>x>>y;
    int **b=new int*[x];
    for(int i=0; i<x; i++)   
        b[i] = new int[y];
    int **a=new int*[x];
    for (int i=0;i<x;i++)
    {
        a[i]=new int[y];
        for (int j=0;j<y;j++)
            in>>a[i][j];
    } 
    in.close();
    if(a[0][0]==0 && a[x-1][y-1]==0)
    {
        out<<"wrong matrix!"<<endl; 
    }
 
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            b[i][j]=0;
        }
    }
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            if(a[i][j]==0)
                a[i][j]=2;
            else
                a[i][j]=1;
        }
    }
 
 
 
    int k=1;
    //b[0][0]=k;
    for(int i=0; i<x; i++)
    {
        for(int j=0; j<y; j++)
        {
            if (i!=0 && j!=0) {
                k=a[i][j]+min(b[i-1][j], b[i][j-1]);
                b[i][j]=k+1;
                k++; 
            } 
        }
    }
    out<<b[x-1][y-1]; 
}
Добавлено через 3 часа 21 минуту
Помогите, ради всего святого!!!!!!!!!!!!!!!!!!!!
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2297 / 1667 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
20.12.2011, 01:23     Задача про минимальный путь в лабиринте. #3
Цитата Сообщение от vikichocolate Посмотреть сообщение
Гляньте, пжл!!!!!Горит очень сильно!!!!Умоляю!!!!!!Подправьте код!!!!!!
Раз уж горит, то, думаю, стоит обратится во Фриланс, там Вам помогут за небольшую плату.
vikichocolate
 Аватар для vikichocolate
25 / 14 / 1
Регистрация: 11.11.2011
Сообщений: 94
20.12.2011, 01:26  [ТС]     Задача про минимальный путь в лабиринте. #4
туда обращаются без какого-либо кода. я эту задачу уже прошу помочь мне сделать месяц, наверное. но никто вообще не хочет помогать...

сама работаю, чтобы есть было что...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.12.2011, 02:19     Задача про минимальный путь в лабиринте. #5
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
#include<iostream>
#include<fstream>
using namespace std;
 
void main()
{
        int x, y ;  // размеры матрицы
        ifstream in;
        in.open("input.txt");
        ofstream  out;
        out.open("output.txt"); 
        in>>x>>y;
        int **b=new int*[x];
        for(int i=0; i<x; i++)   
                b[i] = new int[y];
        int **a=new int*[x];
        for (int i=0;i<x;i++)
        {
                a[i]=new int[y];
                for (int j=0;j<y;j++)
                        in>>a[i][j];
        } 
        in.close();
        if(a[0][0]==0 && a[x-1][y-1]==0)
        {
                out<<"wrong matrix!"<<endl; 
        }
 
        for(int i=0; i<x; i++)
        {
                for(int j=0; j<y; j++)
                {
                        b[i][j]=0;
                }
        }
        b[0][0]=1;
         int k=1;
        while(true)
        {
            bool fl=false;
            int i, j;
            for(i=0; i<x; i++)
                for(j=0; j<y; j++)
                    if(b[i][j]==k)
                    {
                        if(i>0 && a[i-1][j]==0 && b[i-1][j]==0)
                        {
                            b[i-1][j]=k+1;
                            fl=true;
                        }
                        if(i<x-1 && a[i+1][j]==0 && b[i+1][j]==0)
                        {
                            b[i+1][j]=k+1;
                            fl=true;
                        }
                        if(j>0 && a[i][j-1]==0 && b[i][j-1]==0)
                        {
                            b[i][j-1]=k+1;
                            fl=true;
                        }
                        if(j<y-1 && a[i][j+1]==0 && b[i][j+1]==0)
                        {
                            b[i][j+1]=k+1;
                            fl=true;
                        }
                    }
            if(!fl)
                break;
            else
                k++;
        }
        if(b[x-1][y-1]==0)
            out<<"No"<<endl;
        else
        {
            out<<b[x-1][y-1];
 
        }
}
Для таких условий матрица 10*10 подойдет и такой вариант. Проверьте на всякий случай - сам на работоспособность не проверял.
Выводит: No - если пути нет, или если есть путь выводит кол-во пройденных клеток (включая верхнюю левую и нижнюю правую).
vikichocolate
 Аватар для vikichocolate
25 / 14 / 1
Регистрация: 11.11.2011
Сообщений: 94
20.12.2011, 09:47  [ТС]     Задача про минимальный путь в лабиринте. #6
спасибо, что посмотрели. только можете разъяснить немного ваш код.

просто тест
3 3
110
010
011


он неправильно проходит=(((
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.12.2011, 10:01     Задача про минимальный путь в лабиринте. #7
Вот так проверьте:
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
#include<iostream>
#include<fstream>
using namespace std;
 
void main()
{
        int x, y ;  // размеры матрицы
        ifstream in;
        in.open("input.txt");
        ofstream  out;
        out.open("output.txt"); 
        in>>x>>y;
        int **b=new int*[x];
        for(int i=0; i<x; i++)   
                b[i] = new int[y];
        int **a=new int*[x];
        for (int i=0;i<x;i++)
        {
                a[i]=new int[y];
                for (int j=0;j<y;j++)
                        in>>a[i][j];
        } 
        in.close();
        if(a[0][0]==0 && a[x-1][y-1]==0)
        {
                out<<"wrong matrix!"<<endl; 
        }
 
        for(int i=0; i<x; i++)
        {
                for(int j=0; j<y; j++)
                {
                        b[i][j]=0;
                }
        }
                b[0][0]=1;
         int k=1;
        while(true)
                {
                        bool fl=false;
                        int i, j;
                        for(i=0; i<x; i++)
                                for(j=0; j<y; j++)
                                        if(b[i][j]==k)
                                        {
                                                if(i>0 && a[i-1][j]==1 && b[i-1][j]==0)
                                                {
                                                        b[i-1][j]=k+1;
                                                        fl=true;
                                                }
                                                if(i<x-1 && a[i+1][j]==1 && b[i+1][j]==0)
                                                {
                                                        b[i+1][j]=k+1;
                                                        fl=true;
                                                }
                                                if(j>0 && a[i][j-1]==1 && b[i][j-1]==0)
                                                {
                                                        b[i][j-1]=k+1;
                                                        fl=true;
                                                }
                                                if(j<y-1 && a[i][j+1]==1 && b[i][j+1]==0)
                                                {
                                                        b[i][j+1]=k+1;
                                                        fl=true;
                                                }
                                        }
                        if(!fl)
                                break;
                        else
                                k++;
                }
                if(b[x-1][y-1]==0)
                        out<<"No"<<endl;
                else
                {
                        out<<b[x-1][y-1];
 
                }
}
Выдает кол-во пройденных клеток. Т.е. на тест:
3 3
110
010
011
выдаст 5.
Или Вам нужно что бы вывело в файл:
220
020
022
? Тут двойками обозначен сам минимальный путь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2011, 10:23     Задача про минимальный путь в лабиринте.
Еще ссылки по теме:

Задача про Домино-2 C++
Как найти кратчайший путь в лабиринте? C++
Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину C++
C++ Задача "Ладья в Лабиринте"
C++ Задача про зайца

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

Или воспользуйтесь поиском по форуму:
vikichocolate
 Аватар для vikichocolate
25 / 14 / 1
Регистрация: 11.11.2011
Сообщений: 94
20.12.2011, 10:23  [ТС]     Задача про минимальный путь в лабиринте. #8
все! спасибо Вам огромное. месяц мучилась с этой прогой!!!!!!!!!!
Yandex
Объявления
20.12.2011, 10:23     Задача про минимальный путь в лабиринте.
Ответ Создать тему
Опции темы

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