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

Корабли - C++

Восстановить пароль Регистрация
 
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
18.11.2011, 08:47     Корабли #1
Здравствуйте! Ребят, не могли бы вы решить одну задачку на динамику? именно она не получается
была бы вам очень благодарна! заранее большое спасибо вам!
вот задачка:

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

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

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

Пример

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

Вывод
12

Добавлено через 6 часов 36 минут
((((((
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
20.11.2011, 01:16     Корабли #4
Офигенская задача. Подумаю на досуге.
Yandex
Объявления
20.11.2011, 01:16     Корабли
Ответ Создать тему
Опции темы

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