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

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

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

Корабли - C++

18.11.2011, 08:47. Просмотров 593. Ответов 3
Метки нет (Все метки)

Здравствуйте! Ребят, не могли бы вы решить одну задачку на динамику? именно она не получается
была бы вам очень благодарна! заранее большое спасибо вам!
вот задачка:

Дано прямоугольное поле NxM, в клетках которого записаны символы '.' (точка) и '*' (звездочка). За один ход разрешается выбрать один из краев поля (верхний, нижний, левый или правый) шириной (высотой) в 1 клетку и удалить его.
При этом число очков, полученное за этот ход, равно квадрату числа звездочек на этом краю. Процесс продолжается, пока поле состоит хотя бы из одной клетки. Определите максимальное количество очков, которое можно набрать таким способом.

Ввод
В первой строке входного файла заданы натуральные числа N и M (1 <= N, M <= 50). Далее в N строках записано по M символов - клетки поля.

Вывод
Выведите единственное число - ответ на задачу.

Пример

Ввод
3 4
*.*.
..**
.*.*

Вывод
12

Добавлено через 6 часов 36 минут
((((((
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2011, 08:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Корабли (C++):

Расставить корабли в игре Морской Бой - C++
вот сделал игру морсой бой не могу раставить корабли помогите за рание спасибо #include &lt;iostream&gt; #include &lt;iomanip&gt; #include...

Нужно чтобы ИИ в морском бое старался потопить корабли, а подтопленные корабли обводил точками - C#
Нужно написать морской бой, но застрял на написании ИИ противника. Нужно чтобы ИИ старался потопить корабли, а подтопленные корабли обводил...

Корабли в Морском бое - Delphi
Здравствуйте! Я пишу курсач на тему &quot;Морской бой&quot;, и препод нагрузил, чтобы вместо кораблей-клеток, были корабли рисунком (надеюсь Вы меня...

Морской бой. Корабли - C++ WinAPI
Как создать корабли и расположить их в WinAPI?

Корабли пустыни, ну никак не врублюсь. - Pascal
Всем привет. Дали задачки, все остальные решил, а в эту ну ни как не врублюсь! Причем даже есть решение, но никак не могу понять смысл ее...

Морской бой (расставить одиночные корабли) - Prolog
Вводим :show(10, ,,]) получаем: S _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ S _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ S _ _ _ _ _ _ _ _...

3
Aneron
158 / 157 / 12
Регистрация: 20.04.2010
Сообщений: 570
18.11.2011, 09:45 #2
1. Начнем с того что обычно указывается число столбцов(х) потом число строк(у). Так что прямоугольник 3 на 4 будет выглядеть слегка др. образом.
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int ReadSize(char * file_name,int &x,&y)
{
FILE * file;
file = fopen(file_name,"r");
if(!file)
return -1;
else
fscanf(file,"%d %d",&x,&y);
fclose(file);
return 1;
}
int ReadPoints(char * file_name,char * arr)//Return number of readed point.
{
FILE * file;
file = fopen(file_name,"r");
if(!file)
return -1;
int i = 0;
while((c = fgetc(file)) != EOF)
{
if( c ==  '.' || c =='*')
arr[i++] = c;
}
return i;
}
int FindCorner(int i,int j,int x,int y)
{
int result;
if(j => y/2)
result += 2;
if(i => x/2)
result += 1;
return result;
}
bool IsBelongToCorner(int i,int j,int x,int y,int corner_index)
{
if( corner_index < 3 )
if( j => y/2 )
return false;
if(corner_index%2)
if( i > x/2 )
return false;
return true;
}
int FindSquare(char * arr,int corner_index,int x, int y)
//corner_index = 1 for topleft corner,2 for topright,3-for bottomleft,4-for bottomright
{
int sum = 0;
for(int i = 0; i<x;++i)
for(int j = 0; j<y;++j)
if(IsBelongToCorner(i,j,x,y,corner_index))
sum+=arr[i + j*x];
return pow(sum2,2);
}
 
int main()
{
int x,y;
if(!ReadSize("input.txt",x,y))
return -1;//Error
char * arr = new char[x*y]
int readed_size = readPoints("input.txt",arr);
if(readed_size != x*y)
return -1;//Error
int z = x*y;
int i,j,corner,sum = 0;
while(z)
{
i = rand()%x;
j = rand()%y;
if(arr[i+j*x] != '0')
{
corner = FindCorner(i,j,x,y);
sum += FindSquare(arr,corner,x,y);
--z;
}
}
}
return 1;
Не тестировал. И это не готовое решение. Это идея))) Идея теперь у вас есть, так что доводите до ума)))
0
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
19.11.2011, 01:26 #3
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
#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define N 51
 
int d[N][N][N][N], a[N][N], n, m;
 
int sum(int lx, int ly, int rx, int ry) {
    return a[rx][ry] - a[lx - 1][ry] - a[rx][ly - 1] + a[lx - 1][ly - 1];
}
 
int sqr(int x) {
    return x * x;
}
 
int get(int lx, int ly, int rx, int ry) {
    if (lx > rx || ly > ry) return 0;
    int &res = d[lx][ly][rx][ry];
    if (res != -1) return res;
    res = max(max(get(lx + 1, ly, rx, ry) + sqr(sum(lx, ly, lx, ry)),
        get(lx, ly, rx - 1, ry) + sqr(sum(rx, ly, rx, ry))),
        max(get(lx, ly + 1, rx, ry) + sqr(sum(lx, ly, rx, ly)),
        get(lx, ly, rx, ry - 1) + sqr(sum(lx, ry, rx, ry))));
    return res;
}
 
int main() {
    memset(d, 255, sizeof d);
    scanf("%d%d", &n, &m);
 
    for(int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for(int j = 1; j <= m; ++j)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + (s[j - 1] == '*' ? 1 : 0);
    }
    
    cout << get(1, 1, n, m);
 
    return 0;
}
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
20.11.2011, 01:16 #4
Офигенская задача. Подумаю на досуге.
0
20.11.2011, 01:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2011, 01:16
Привет! Вот еще темы с ответами:

Морской бой, как расставить корабли? - C++ Builder
Делаю игру Морской бой, используя DrawGrid Как расставить корабли?

Игра морской бой - как расставлять корабли - C#
Решил написать игру чтоб опыта набраться. Вот возникла проблема: в верху формы расположены 4 кнопки(4вида кораблей) и ниже расположено...

Определить страны, в которые никогда не приходят корабли с целью 'туризм'. - MS Access
Всем доброго вечера. Определить страны, в которые никогда не приходят корабли с целью 'туризм'. Я смог вывести страны в которые...

Игра морской бой: никак не придумаю как лучше реализовать корабли в игре - C#
Пишу игру &quot;Морской бой&quot; на c# и никак не решу как лучше реализовать в программе корабли.


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

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

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