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

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

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


Разработать программу, которая ищет минимальный путь в лабиринте. Лабиринт представляет собой матрицу 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]; 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2011, 19:03     Задача про минимальный путь в лабиринте.
Посмотрите здесь:

Задача про матрицу C++
C++ Задача про водопровод
Найти минимальный путь на земельном участке вдоль ограждения C++
Задача про рюкзак C++
Задача про температуру C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
2293 / 1663 / 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
4660 / 2486 / 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
4660 / 2486 / 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     Задача про минимальный путь в лабиринте.
Еще ссылки по теме:

Задача про торт C++
C++ Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Как найти кратчайший путь в лабиринте? C++

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

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

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