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

@APELSINO4KA · Регистрация: 30.03.2014

Author24 — интернет-сервис помощи студентам

Само условие
Битва между офисами
Время: 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

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, ребят,подскажите,хоть куда смотреть....=(

ФедосеевПавел · 08.03.2015, 09:07

Для начала определиться с ошибкой. Для 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М.

ФедосеевПавел Модератор 8477 / 4335 / 1643 Регистрация: 01.02.2015 Сообщений: 13,462 Записей в блоге: 8
	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(nm)/4=25{10}^{6}$ . 2. Просматривать a слева-направо сверху-вниз. 3. Встретилась непустая клетка. - Если слева и сверху нет соседей, то это новый корабль. Номер нового корабля записываем в a вместо состояния (S или X). - Если есть соседи, то в текущей клетке продолжение "известного" корабля. Модифицируем состояние корабля (допустим, что до сих пор состояние было "целый", а текущая клетка "Х", меняем состояние на "ранен"). - Может получится, что из-за изогнутости корабля мы считали его как два разных, но вот в текущей клетке "разные" корабли встретились. Модифицируем состояние корабля с меньшим номером, а корабль с большим номером удаляем (в состояние "отсутствует"). Здесь "минус" в нерациональном расходе памяти (массив кораблей, увеличение разрядности элементов поля), а "плюс" в переносе памяти из стека в сегмент данных (или в кучу). Можно немного оптимизировать расход памяти на массив кораблей, разрядность матрицы a, за счёт соображения, что одновременно может рассматриваться не более max(n,m)/2 кораблей (т.е. не более 5*10^3), но это усложнит алгоритм, а памяти можно выделять до 128М. 0