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

Маршрут в таблице - C++

Восстановить пароль Регистрация
 
$Rockstar$
Сообщений: n/a
30.06.2011, 11:02     Маршрут в таблице #1
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов.
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Please, help me) Language: C.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2011, 11:02     Маршрут в таблице
Посмотрите здесь:

Маршрут C++
C++ Маршрут
C++ Кратчайший маршрут
Шифр гронсфельда + маршрут Гамильтона C++
Маршрут Bus C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CJIABYH9
0 / 0 / 0
Регистрация: 26.04.2012
Сообщений: 3
26.04.2012, 01:52     Маршрут в таблице #2
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
#include "StdAfx.h"
#include <iostream>
#include <windows.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "russian");
    int n=0;
    
    cout<<"Введiть N – число рядкiв i стовпцiв: ";
    cin>>n;
    cout<<endl;
    int mas[255][255];
    char masc[255][255];
    srand((unsigned)time(NULL));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            mas[i][j]=rand()%(9-1)+1;
            cout<<mas[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            masc[i][j]= '-' ;
        }
    }
 
    masc[0][0]='#';
    int i=0;
    int j=0;
    int ms=mas[0][0];
    do 
    {
        if(i==n-1)
        {
            ms=ms+mas[i][j]+mas[i][j+1];
            masc[i][j+1]='#';
            j=j+1;
        }
        else
        {
            if(j==n-1)
            {
                ms=ms+mas[i][j]+mas[i+1][j];
                masc[i+1][j]='#';
                i=i+1;
            }
            else
            {
                if (mas[i][j]+mas[i][j+1]<mas[i][j]+mas[i+1][j])
                {
                    ms=ms+mas[i][j]+mas[i][j+1];
                    masc[i][j+1]='#';
                    j=j+1;
                }
                else 
                {
                    ms=ms+mas[i][j]+mas[i+1][j];
                    masc[i+1][j]='#';
                    i=i+1;
                }
            }
        }
    }
    while (masc[n-1][n-1]!='#');
 
    cout<<endl;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout<<masc[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    cout<<"Мiнiмальна сума цифр в клiтинках= "<<ms<<endl;
    //Made by Yaroslav Trygubenko, 202-TN, ITTS, PNTU,m. Poltava 2012
    system("pause");
    return 0;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
26.04.2012, 02:21     Маршрут в таблице #3
Цитата Сообщение от CJIABYH9 Посмотреть сообщение
C++
1
mas[i][j]=rand()%(9-1)+1;
C++
1
mas[i][j]=rand()%10;
, не?

Я бы присмотрелся к Алгоритму Дейкстры на взвешанном графе.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.04.2012, 05:32     Маршрут в таблице #4
Цитата Сообщение от MrGluck Посмотреть сообщение
Я бы присмотрелся к Алгоритму Дейкстры на взвешанном графе.
Лучше ДП здесь не придумаешь.
CJIABYH9
0 / 0 / 0
Регистрация: 26.04.2012
Сообщений: 3
26.04.2012, 19:17     Маршрут в таблице #5
ну да можно и так, протупил!

Добавлено через 9 минут
valeriikozlov, я не против, но где ваши примери?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.04.2012, 19:53     Маршрут в таблице #6
Цитата Сообщение от CJIABYH9 Посмотреть сообщение
valeriikozlov, я не против, но где ваши примери?
Без них ни как?
Когда-то давно решал вот эту задачу:
http://********/index.asp?main=task&id_task=368
Вот код решения:
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
#include <stdio.h>
 
int main(){
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 int N, **mas, **mas1, **mas23, i, j;// 1-вниз, 2-вправо
 char **mas_ch, ch;
 scanf("%d\n",&N);
 mas=new int*[N];
 mas1=new int*[N];
 mas23=new int*[N];
 mas_ch=new char*[N];
 for(i=0; i<N; i++)
 {
     mas[i]=new int[N];
     mas1[i]=new int[N];
     mas23[i]=new int[N];
     mas_ch[i]=new char[N];
 }
 for(i=0; i<N; i++)
 {
     for(j=0; j<N; j++)
     {
         scanf("%c", &ch);
         mas[i][j]=(int)(ch-'0');
         mas_ch[i][j]='.';
     }
     scanf("\n");
 }
 mas1[0][0]=mas[0][0];
 for(i=1; i<N; i++)
 {
     mas1[0][i]=mas1[0][i-1]+mas[0][i];
     mas1[i][0]=mas1[i-1][0]+mas[i][0];
     mas23[0][i]=2;
     mas23[i][0]=1;
 }
 for(i=1; i<N; i++)
 {
     for(j=i; j<N; j++)
         if(mas1[i-1][j]<mas1[i][j-1])
         {
             mas1[i][j]=mas[i][j]+mas1[i-1][j];
             mas23[i][j]=1;
         }
         else
         {
             mas1[i][j]=mas[i][j]+mas1[i][j-1];
             mas23[i][j]=2;
         }
    for(j=i+1; j<N; j++)
        if(mas1[j-1][i]<mas1[j][i-1])
        {
            mas1[j][i]=mas1[j-1][i]+mas[j][i];
            mas23[j][i]=1;
        }
        else
        {
            mas1[j][i]=mas1[j][i-1]+mas[j][i];
            mas23[j][i]=2;
        }
 }
 int temp_i=N-1, temp_j=N-1, fl=1;
 while(fl)
 {
     if(mas23[temp_i][temp_j]==1)
     {
         temp_i--;
         mas_ch[temp_i][temp_j]='#';
     }
     else
     {
         temp_j--;
         mas_ch[temp_i][temp_j]='#';
     }    
     if(temp_i==0 && temp_j==0)
         fl=0;
 }
 mas_ch[0][0]=mas_ch[N-1][N-1]='#';
 for(i=0; i<N; i++)
 {
     for(j=0; j<N; j++)
         printf("%c", mas_ch[i][j]);
     printf("\n");
 }
  return 0;
}
Сейчас бы написал более компактный код, с использованием всего двух двумерных массивов, но не буду. Разбирайтесь, пробуйте написать короче, если есть желание.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.04.2012, 23:18     Маршрут в таблице
Еще ссылки по теме:

C++ программа шахматы (маршрут коня)
Найти кратчайший маршрут C++
C++ Оптимальный маршрут почтальона

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

Или воспользуйтесь поиском по форуму:
CJIABYH9
0 / 0 / 0
Регистрация: 26.04.2012
Сообщений: 3
26.04.2012, 23:18     Маршрут в таблице #7
valeriikozlov, я же только учусь просто! и + сдесь не было решения. мало ли может кому то пригодится.
Yandex
Объявления
26.04.2012, 23:18     Маршрут в таблице
Ответ Создать тему
Опции темы

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