Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 30.03.2014
Сообщений: 3
1

Битва между офисами в морской бой

08.03.2015, 00:38. Просмотров 951. Ответов 1
Метки нет (Все метки)


Само условие
Битва между офисами
Время: 1000ms, Память: 128MB, Сложность: 30%; Попытка: 11, Начислено баллов: 0
Среди офисных работников ряда предприятий в свое время была популярная игра "Морской бой". Игра ведется на прямоугольном поле произвольных размеров N×M (1≤ N, M ≤ 10^4), где N - количество строк, M - количество столбцов. Приближается чемпионат между офисами по морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.
Корабль на поле — это связанная фигура, стоящая из одной или нескольких рядом лежащих клеток, имеющих общую сторону. Корабли могут быть абсолютно любых форм и размеров!
Входные данные: Выходные данные:
Первая строка входного потока содержит два целых числа N и M, разделённых пробелами - размеры игрового поля. Далее идут N строк по M символов - описание игрового поля.
Латинская буква 'X' обозначает подбитую клетку корабля, а 'S' — не подбитая клетка корабля, '-' — свободное водное пространство.
В выходной поток вывести три числа, каждое в отдельной строке:
количество целых кораблей
количество подбитых кораблей
количество уничтоженных кораблей
Пример входного файла (input.txt):
3 8
---SSS--
XX--S-X-
X-S---S-
Решение
Pascal
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
var
s:ansistring;
a:array [-999..9999,-999..9999] of longint;
i,n,m,j,lov1,lov2,lov3,k1,k2,x,y:longint;
Procedure ap(x,y:longint);
begin
if a[x,y]=1 then inc (k1) 
else if a[x,y]=-1 then inc (k2); 
a[x,y]:=-2; 
if (x>1) then if (a[x-1,y]<>-2)and(a[x-1,y]<>0) then ap(x-1,y);
if (x<n) then if (a[x+1,y]<>-2)and(a[x+1,y]<>0) then ap(x+1,y);
if (y>1) then if (a[x,y-1]<>-2)and(a[x,y-1]<>0) then ap(x,y-1);
if (y<m) then if (a[x,y+1]<>-2)and(a[x,y+1]<>0) then ap(x,y+1);
end;
begin
readln (n,m);
for i:=0 to n+1 do
for j:=0 to m+1 do
a[i,j]:=-2;
for i:=1 to n do begin
readln (s);
for j:=1 to m do begin
if s[j]='-' then a[i,j]:=0;
if s[j]='S' then a[i,j]:=1;
if s[j]='X' then a[i,j]:=-1;
end;
end;
 
for i:=1 to n do begin
k1:=0; k2:=0;
for j:=1 to m do
if (a[i,j]<>0)and(a[i,j]<>-10) then begin
k1:=0; k2:=0;
x:=i; y:=j;
if (x>0)and(y>0)and(x<=n)and(Y<=m) then ap(x,y);
if (k1>0)and(k2=0) then inc (lov1);
if (k1>0)and(k2>0) then inc (lov2);
if (k1=0)and(k2>0) then inc (lov3);
end;
end;
writeln (lov1,' ',lov2,' ',lov3);
end.
Проблема,в том,что проходит все тесты кроме одного , на нем выдает ошибку 202, ребят,подскажите,хоть куда смотреть....=(
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.03.2015, 00:38
Ответы с готовыми решениями:

«Морской бой» - на Pascal
Имеется такой код. он отчасти рабочий, для начала напишу задание: «Морской бой» Первая строка...

Матрица. морской бой
Написать программу подсчета одно-, двух-, трех- и четырехпалубных кораблей, расположенных на поле...

Морской бой: написать проверку для расстановки последнего корабля
program morskoi_boy ; var m, n: integer; a: array of char; f1, f2: text ; ...

Морской бой
Поле для игры в морской бой имеет размер N x N клеток. Клетки, занятые кораблями, содержат символ...

1
Модератор
Эксперт по электронике
7476 / 3677 / 1444
Регистрация: 01.02.2015
Сообщений: 11,454
Записей в блоге: 2
08.03.2015, 09:07 2
Для начала определиться с ошибкой. Для FreePascal читаем "user.pdf" раздел "Run-time errors"
202 Stack overflow error The stack has grown beyond its maximum size (in which case the size of
local variables should be reduced to avoid this error), or the stack has become corrupt. This
error is only reported when stack checking is enabled.
Единственная возможность - рекурсивнный вызов процедуры ap. Может быть тест - поле 10000х10000, и один сплошной корабль.

Ещё, по условию m и n <=10^4, а матрица определена до 9999.

Никаких мыслей по исправлению, особо, нет. Может быть пойти другим путём решения. Или попробовать директивы компиляции, изменяющие размер стека $MEMORY или $MINSTACKSIZE (см. "prog.pdf").

Добавлено через 33 минуты
Другой путь (нерекурсивный):
1. Завести байтовый массив состояний каждого корабля (отсутствует, целый, уничтоженный, раненый) он по размерам не будет превышать https://www.cyberforum.ru/cgi-bin/latex.cgi?max(n*m)/4=25*{10}^{6}.
2. Просматривать a слева-направо сверху-вниз.
3. Встретилась непустая клетка.
- Если слева и сверху нет соседей, то это новый корабль. Номер нового корабля записываем в a вместо состояния (S или X).
- Если есть соседи, то в текущей клетке продолжение "известного" корабля. Модифицируем состояние корабля (допустим, что до сих пор состояние было "целый", а текущая клетка "Х", меняем состояние на "ранен").
- Может получится, что из-за изогнутости корабля мы считали его как два разных, но вот в текущей клетке "разные" корабли встретились. Модифицируем состояние корабля с меньшим номером, а корабль с большим номером удаляем (в состояние "отсутствует").

Здесь "минус" в нерациональном расходе памяти (массив кораблей, увеличение разрядности элементов поля), а "плюс" в переносе памяти из стека в сегмент данных (или в кучу).
Можно немного оптимизировать расход памяти на массив кораблей, разрядность матрицы a, за счёт соображения, что одновременно может рассматриваться не более max(n,m)/2 кораблей (т.е. не более 5*10^3), но это усложнит алгоритм, а памяти можно выделять до 128М.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.03.2015, 09:07

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Игра "Морской бой"
Здравствуйте, мне нужна помощь в реализации игры морской бой, сложность в том, что игра должна быть...

Процедура стрельбы. Морской бой
Напишите пожалуйста процедуру стрельбы по случайному принципу без повторного выстрела в одно и то...

Морской бой - запрограммировать ход компьютера
Такая проблема, я не знаю как правильно реализовать ход компьютера. Рандомом бъёт по случайной...

Игра "Морской бой"
Нужна игра сделанная на turbo pascal.


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

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

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