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

Минимальный путь из левой верхней в правую нижнюю клетку таблицы. - C++

Восстановить пароль Регистрация
 
copybook123
0 / 0 / 0
Регистрация: 11.12.2013
Сообщений: 3
30.01.2014, 14:52     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #1
Не могу понять в чем ошибка...помогите.
Химическая тревога
(Время: 1 сек. Память: 16 Мб Сложность: 50%)
Произошло радиоактивное заражение местности. Составлена карта зараженности. Она представляет собой прямоугольную таблицу N*M, в клетках которой записана зараженность соответствующего участка.

Требуется написать программу, которая найдет путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации.

Входные данные

Входной файл INPUT.TXT содержит в первой строке числа N и M, а в следующих N строках – по M чисел – карта зараженности местности. Числа в строках разделяются одним пробелом. 1<=N<=30, 1<=M<=30, зараженность участка – целое число от 0 до 100.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число – суммарную долю радиации.
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
#include<iostream>
using namespace std;
int n,m,a[100][100],sum=0,way[100][100];
void fuc(int y,int x)
{
   if(y==n-1 && x==m-1)
      return;
      
   
   if(y!=n-1 && way[y][x]+a[y+1][x]<way[y+1][x])
   {
      way[y+1][x]=way[y][x]+a[y+1][x];
      fuc(y+1,x);
   }
   
   if(y!=0 && way[y][x]+a[y-1][x]<way[y-1][x])
   {
      way[y-1][x]=way[y][x]+a[y-1][x];
      fuc(y-1,x);
   }
   ///////////////////
    if(x!=n-1 && way[y][x]+a[y][x+1]<way[y][x+1])
   {
      way[y][x+1]=way[y][x]+a[y][x+1];
      fuc(y,x+1);
   }
   
   if(y!=0 && way[y][x]+a[y][x-1]<way[y][x-1])
   {
      way[y][x-1]=way[y][x]+a[y][x-1];
      fuc(y,x-1);
   }  
   
}
int main()
{
   int i,j;
   cin>>n>>m;
   for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
         cin>>a[i][j];
         way[i][j]=1000*1000;
      }
   way[0][0]=a[0][0];
  
   fuc(0,0);
   
   
   
   for(i=0;i<5;i++)
   {
      for(j=0;j<5;j++)
         cout<<way[i][j]<<" ";
      cout<<endl;
   }
 
 
system("pause");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 14:52     Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Посмотрите здесь:

C++ Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
Задача про минимальный путь в лабиринте. C++
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N C++
C++ Заполнить квадрат углами и оставить одну пустую клетку
Определить минимальный элемент квадратной матрицы, расположенный в левой части, ограничен диагоналями, включая диагональные элементы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
egor2116
 Аватар для egor2116
337 / 368 / 42
Регистрация: 20.01.2013
Сообщений: 1,100
30.01.2014, 14:58     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #2
Возможно стоит почитать про алгоритмы поиска пути(такие как A*, скачка, волновой и т.д.)
Enotniy
 Аватар для Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
30.01.2014, 15:03     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #3
copybook123, как я понимаю просто идёте в ту клетку в которой меньше радиации? Для правильного ответа вам нужно воспользоваться алгоритмом Дейкстры.
copybook123
0 / 0 / 0
Регистрация: 11.12.2013
Сообщений: 3
30.01.2014, 15:11  [ТС]     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #4
я не могу понять почему выводит во так...

2 102 7 1000000 1000000
3 103 7 1000000 1000000
4 4 7 1000000 1000000
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.01.2014, 17:31     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #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
#include<iostream>
using namespace std;
int n,m,a[100][100],sum=0,way[100][100];
 
int main()
{
   int i,j;
   cin>>n>>m;
   for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
         cin>>a[i][j];
         //way[i][j]=1000*1000;
      }
   way[0][0]=a[0][0];
   for(i=1;i<n;i++)
    way[i][0]=a[i][0]+way[i-1][0];
   for(i=0;i<n;i++)   
      for(j=1;j<m;j++)
      {
        if(i==0)
          way[i][j]=a[i][j]+way[i][j-1];
        else
          if(way[i-1][j]<way[i][j-1])
            way[i][j]=a[i][j]+way[i-1][j];
          else
            way[i][j]=a[i][j]+way[i][j-1];          
      }
    
  
   //fuc(0,0);
   
   
   
   cout<<way[n-1][m-1]<<endl;
 
system("pause");
return 0;
}
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
30.01.2014, 17:41     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #6
valeriikozlov, там не сказано, что двигаться можно только вправо и вниз.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.01.2014, 20:31     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #7
Цитата Сообщение от Somebody Посмотреть сообщение
valeriikozlov, там не сказано, что двигаться можно только вправо и вниз.
тогда попозже отпишусь, когда компилятор под рукой будет (если решение не найдется).

Добавлено через 2 часа 48 минут
код писать пока рано.
copybook123, см комментарии
Цитата Сообщение от copybook123 Посмотреть сообщение
if(y!=n-1 && way[y][x]+a[y+1][x]<way[y+1][x])
* *{
* * * way[y+1][x]=way[y][x]+a[y+1][x];
* * * fuc(y+1,x);
* *}
if(y!=0 && way[y][x]+a[y-1][x]<way[y-1][x])
* *{
* * * way[y-1][x]=way[y][x]+a[y-1][x];
* * * fuc(y-1,x);
* *}
* *///////////////////
* * if(x!=n-1 && way[y][x]+a[y][x+1]<way[y][x+1])// вот в этой строке x нужно сравнивать не c n-1, а с m-1
* *{
* * * way[y][x+1]=way[y][x]+a[y][x+1];
* * * fuc(y,x+1);
* *}
if(y!=0 && way[y][x]+a[y][x-1]<way[y][x-1])// вот в этой строке не y нужно сравнивать с 0, а x
* *{
* * * way[y][x-1]=way[y][x]+a[y][x-1];
* * * fuc(y,x-1);
* *}
Далее вывод:
Цитата Сообщение от copybook123 Посмотреть сообщение
for(i=0;i<5;i++)// наверное лучше использовать не 5, а n
* *{
* * * for(j=0;j<5;j++)// наверное лучше использовать не 5, а m
* * * * *cout<<way[i][j]<<" ";
* * * cout<<endl;
* *}
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
30.01.2014, 21:45     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #8
Я НЕ ПОНЯЛ. ЗАРАЖЕНИЕ ХИМИЧЕСКОЕ ИЛИ РАДИАЦИОННОЕ?

ПОХОЖЕ, УСЛОВИЕ ЗАДАЧИ НЕКОРРЕКТНО! В ОДНОМ МЕСТЕ РЕЧЬ о химическом - в другом нет!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 22:15     Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Еще ссылки по теме:

Найти минимальный путь на земельном участке вдоль ограждения C++
C++ Вывести массив на экран в виде таблицы, в конце каждой строки надо вывести минимальный элемент
Поменять местами левую верхнюю и правую нижнюю четверти матрицы - С и C++ C++

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

Или воспользуйтесь поиском по форуму:
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
30.01.2014, 22:15     Минимальный путь из левой верхней в правую нижнюю клетку таблицы. #9
Заражение везде радиационное, только тревога химическая. Спасибо, что хоть так, а то ведь у нас вообще ничего не скажут...
А алгоритм Дейчстры был бы очень даже в тему вместо стапятисот условий.
Yandex
Объявления
30.01.2014, 22:15     Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Ответ Создать тему
Опции темы

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