Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
copybook123
0 / 0 / 0
Регистрация: 11.12.2013
Сообщений: 3
#1

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

30.01.2014, 14:52. Просмотров 905. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 14:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальный путь из левой верхней в правую нижнюю клетку таблицы. (C++):

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. - C++
кому не трудно помогите сделать. если не трудно вам написать код. Дана прямоугольная таблица nxn клеток. В каждой клетке содержится...

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

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

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

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

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

8
egor2116
342 / 373 / 42
Регистрация: 20.01.2013
Сообщений: 1,132
30.01.2014, 14:58 #2
Возможно стоит почитать про алгоритмы поиска пути(такие как A*, скачка, волновой и т.д.)
0
Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
30.01.2014, 15:03 #3
copybook123, как я понимаю просто идёте в ту клетку в которой меньше радиации? Для правильного ответа вам нужно воспользоваться алгоритмом Дейкстры.
1
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
0
valeriikozlov
Эксперт С++
4673 / 2499 / 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;
}
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
30.01.2014, 17:41 #6
valeriikozlov, там не сказано, что двигаться можно только вправо и вниз.
0
valeriikozlov
Эксперт С++
4673 / 2499 / 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;
* *}
0
Kuzia domovenok
1951 / 1804 / 140
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
30.01.2014, 21:45 #8
Я НЕ ПОНЯЛ. ЗАРАЖЕНИЕ ХИМИЧЕСКОЕ ИЛИ РАДИАЦИОННОЕ?

ПОХОЖЕ, УСЛОВИЕ ЗАДАЧИ НЕКОРРЕКТНО! В ОДНОМ МЕСТЕ РЕЧЬ о химическом - в другом нет!
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
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
Привет! Вот еще темы с ответами:

Найти путь из левой верхней ячейки в правую нижнюю ячейку матрицы - C#
Нужна помощь, переделать код из Pascal в C# даже лучше если в (Windows Form) Const InputFile='Input.txt' ; OutputFile='Ouput.txt'...

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

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

Graphics.DrawEllipse() обрезает нижнюю и правую границы круга - C#
Здравствуйте. Простите за глупый вопрос, но самому исправить не получилось. Имеется рисование эллипса: public override void...


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

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

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