Питон 17 .
в левом верхнем углу прямоугольной таблицы размером n×m находится черепашка. в каждой клетке таблицы записано некоторое число. черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
входные данные
в первой строке входных данных записаны два натуральных числа n и m, не превосходящих 100 — размеры таблицы. далее идет n строк, каждая из которых содержит m чисел, разделенных пробелами — описание таблицы. все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
выходные данные
первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. маршрут выводится в виде последовательности, которая должна содержать n-1 букву d, означающую передвижение вниз и m-1 букву r, означающую передвижение направо. если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
примеры
входные данные
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
выходные данные
74
d d r r r r d d
using System;
class Program
{
static void Main()
{
int x1 = 2, y1 = 1;
int x2 = 6, y2 = 5;
int x3 = 10, y3 = 1;
var a = Distance(x2, y2, x3, y3);
var b = Distance(x1, y1, x3, y3);
var c = Distance(x2, y2, x1, y1);
Console.WriteLine("S = {0}", Square(a, b, c));
Console.ReadKey();
}
//растояние между точками
static double Distance(int x1, int y1, int x2, int y2)
{
return Math.Sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
//формула герона
static double Square(double a, double b, double c)
{
var p = (a + b + c) / 2;
return Math.Sqrt(p * (p - a) * (p - b) * (p - c));
}
// теорема косинусов
static double Angle(double a, double b, double c)
{
return Math.Acos((b * b + c * c - a * a) / (2 * b * c));
}
static bool IsAcuteAngel(double alpha)
{
return alpha < Math.PI / 2;
}
}
#include <iostream>
using namespace std;
int main()
{
int n; cout << "розмір квадратної матриці = ";
cin >> n;
int mt[n][n]; // оголошення матриці розмірністю n*m, де n = m = n
srand(time(NULL));
cout << "була: " << endl;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mt[i][j]=rand()%21-10; // генерація випадкових чисел в матриці
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << " " << mt[i][j]; // вивід матриці
cout << endl;
}
cout << endl << "стала: " << endl;
for (int i = 0; i < n; i++) //індексація масивів у C++ завжди з 0, тому ДО n
{
int* temp=new int[n]; // видозмінити матрицю (двовимірний масив) можна за до одновимірного динамічного масиву temp[n] або змінної temp
temp[i] = mt[n-1][i]; // записати ("покласти") в масив temp "копію" останнього (n-1) рядка матриці
mt[n-1][i] = mt[i][0]; // останній (n-1) рядок матриці обернути на перший (нульовий) стовпець матриці
mt[i][0] = temp[i]; // перший (нульовий) стовпець обернути на «копію» останнього (n-1) рядка, яка міститься в допоміжному масиві temp (зчитати з temp)
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << " " << mt[i][j]; // вивід видозміненої матриці
cout << endl;
}
return 0; }