Форум программистов, компьютерный форум CyberForum.ru

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

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

Корабли - C++

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

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

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

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

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

Пример

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

Вывод
12

Добавлено через 6 часов 36 минут
((((((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2011, 08:47     Корабли
Посмотрите здесь:

Игра морской бой - как расставлять корабли C#
К Земле летят гигантские космические корабли инопланетян
Pascal Корабли пустыни, ну никак не врублюсь.
Корабли в Морском бое Delphi
Морской бой, как расставить корабли? C++ Builder
C++ Расставить корабли в игре Морской Бой
C# Нужно чтобы ИИ в морском бое старался потопить корабли, а подтопленные корабли обводил точками
Морской бой (расставить одиночные корабли) Prolog
Морской бой. Корабли C++ WinAPI
Определить страны, в которые никогда не приходят корабли с целью 'туризм'. MS Access

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aneron
 Аватар для Aneron
157 / 156 / 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;
Не тестировал. И это не готовое решение. Это идея))) Идея теперь у вас есть, так что доводите до ума)))
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;
}
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
20.11.2011, 01:16     Корабли #4
Офигенская задача. Подумаю на досуге.
Yandex
Объявления
20.11.2011, 01:16     Корабли
Ответ Создать тему
Опции темы

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