Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
Формат ввода
В первой строке входного файла записаны числа n и m "— размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» "— север, «S» "— юг, «E» "— восток, «W» "— запад.
Формат вывода
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.
Пример 1Ввод
1 5
WN.SE
Вывод
4
Пример 2Ввод
1 3
E.W
Вывод
0
Пример 3Ввод
3 4
.N.W
WWSS
EWEW
Вывод
4
Подскажите, пожалуйста, как ускорить код? Часть тестов код проходит правильно, а остальное - TL (Time Limit). Как ускорить выполнение код, чтобы не было TL?
var
c, r, rows, cols, row, col, count, pred: integer;
a: array [,] of Integer;
Yes: boolean;
s: string;
begin
readln(rows, cols);
Setlength(a, rows, cols);
for row := 0 to rows - 1 do
begin
Readln(s);
for col := 0 to cols - 1 do
case s[col + 1] of
'.': a[row, col] := 0;
'N': a[row, col] := 1;
'S': a[row, col] := 2;
'E': a[row, col] := 3;
'W': a[row, col] := 4;
end;
end;
count := 0;
repeat
pred := count;
for row := 0 to rows - 1 do
for col := 0 to cols - 1 do
if a[row, col] > 0 then
begin
Yes := True;
case a[row, col] of
1:
for r := row - 1 downto 0 do // N : row-1
if a[r, col] > 0 Then
begin
Yes := False;
break;
end;
2:
for r := row + 1 to rows - 1 do // S : row+1
if a[r, col] > 0 Then
begin
Yes := False;
break;
end;
3:
for c := col + 1 to cols - 1 do // E : col+1
if a[row, c] > 0 Then
begin
Yes := False;
break;
end;
4:
for c := col - 1 downto 0 do // W : col-1
if a[row, c] > 0 Then
begin
Yes := False;
break;
end;
end;
if Yes then
begin
a[row, col] := 0;
count += 1;
end;
end;
if pred = count then Break;
until False;
writeln(count);
end.
Протестировать решение:
https://contest.yandex.ru/roi/contest/999/enter 
