Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
copybook123
0 / 0 / 1
Регистрация: 11.12.2013
Сообщений: 3
#1

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

30.01.2014, 14:52. Просмотров 1034. Ответов 8
Метки нет (Все метки)

Не могу понять в чем ошибка...помогите.
Химическая тревога
(Время: 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;
}

http://www.cyberforum.ru/cpp-beginners/thread377422.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 14:52
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Минимальный путь из левой верхней в правую нижнюю клетку таблицы. (C++):

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

Поменять местами левую верхнюю и правую нижнюю четверти матрицы (с указателями)
есть задача Дана матрица размера M × N (M и N — четные числа). Поменять...

Нули массива, размещены в левой и верхней четвертях матрицы
Сохранить нулевые элементы массива, которые размещены в левой и верхней...

Пройти по заданному графу с крайней левой вершины в правую, использовав все рёбра по одному разу
Существует граф, по которому нужно пройти с крайней левой вершины в правую,...

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется...

8
egor2116
571 / 375 / 215
Регистрация: 20.01.2013
Сообщений: 1,135
30.01.2014, 14:58 #2
Возможно стоит почитать про алгоритмы поиска пути(такие как A*, скачка, волновой и т.д.)
0
Enotniy
98 / 99 / 31
Регистрация: 15.01.2014
Сообщений: 283
30.01.2014, 15:03 #3
copybook123, как я понимаю просто идёте в ту клетку в которой меньше радиации? Для правильного ответа вам нужно воспользоваться алгоритмом Дейкстры.
1
copybook123
0 / 0 / 1
Регистрация: 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
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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;
}
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,211
Завершенные тесты: 3
30.01.2014, 17:41 #6
valeriikozlov, там не сказано, что двигаться можно только вправо и вниз.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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;
* *}
0
Kuzia domovenok
2207 / 1976 / 443
Регистрация: 25.03.2012
Сообщений: 6,923
Записей в блоге: 1
30.01.2014, 21:45 #8
Я НЕ ПОНЯЛ. ЗАРАЖЕНИЕ ХИМИЧЕСКОЕ ИЛИ РАДИАЦИОННОЕ?

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

Найти путь из левой верхней ячейки в правую нижнюю ячейку матрицы
Нужна помощь, переделать код из Pascal в C# даже лучше если в (Windows Form) ...

Отображение данных в левой верхней ячейке первой таблицы, входящей в файл
Не знаю даже за что зацепиться, т.к я в этом полный аут, дан html файл написать...

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

Как правильно вычислить правую и нижнюю границу блоков?
Имеется блок, внутри которого расположены несколько разных по размеру блоков,...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru