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

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

30.01.2014, 14:52. Просмотров 1068. Ответов 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
Готовые ответы и решения:

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

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

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

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

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

8
Другие темы раздела
C++ Создать интерфейс к программе http://www.cyberforum.ru/cpp-beginners/thread1085367.html
Я написал программу подскажите пожалуйста как мне написать простенький интерфейс к ней с помощью каких средств
C++ Сформировать квадратную матрицу порядка n по заданному образцу Сформировать квадратную матрицу порядка n по заданному образцу 0 0 0 … 0 0 0 1 0 … 0 0 0 0 2 … 0 0 ……………………. 0 0 0 … 0 n-1 http://www.cyberforum.ru/cpp-beginners/thread1085351.html
C++ Написать функцию проверяющую есть ли отрицательные элементы в указанной строке двумерного массива
1. Написать функцию проверяющую есть ли отрицательные элементы в указанной строке двумерного массива. Удалить из массива все строки с отрицательными элементами, удаленная строка заполняется 0 и...
C++ Определить лежит ли один треугольник в другом
Треугольник задается координатами своих вершин. По двум треугольникам определить лежит ли один из них в другом. Если да, вычислить площадь той части внешнего треугольника, которая не принадлежит...
C++ Библиотека Обработки строк string.h http://www.cyberforum.ru/cpp-beginners/thread1085329.html
Задание таково: Разработайте программу работы со строками. Организуйте ввод исходных данных с клавиатуры. Используйте функции из библиотеки обработки строк string.h. Результаты работы программы...
C++ Структура со сложными полями не читается Есть тип-структура с различными полями - юнионами и структурами. Но почему-то в исходной форме компилятор не видит эти поля и ругается, что "MyType has no member named <...>". typedef struct { ... подробнее
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru