ABCPascal.Net. Olympiad problem, how to speed up the code?

Question

Pascal

Robinson lives on an island, which is a rectangle of n × m cells.
Several crocodiles crawled out to Robinson Island to bask in the sun and dozed off. Robinson wants to drive the troublesome neighbors away without making a fuss. To do this, he throws nuts at the dormant crocodiles.
In each cell of the island there is no more than one crocodile. Frightened by a nut, the crocodile quickly runs in a straight line until it is in the water. Each crocodile knows the direction in which it will run if startled. The directions in which the crocodiles will run are parallel to the sides of the island.
If there is another crocodile in the path of the frightened crocodile, then, having collided, they will get angry and attack Robinson. Therefore, it is necessary to carefully choose the next crocodile, so that only empty cells are on its way.
Robinson does not throw another nut until the previous crocodile is in the water.
It is required to write a program that determines the maximum number of crocodiles that can be driven away without making them angry.
Input Format
The first line of the input file contains the numbers n and m "- the size of the island from north to south and from west to east. The next n lines of m characters each describe the current location of the crocodiles on the island. If the cage is free, then it is denoted by a dot "." , and if there is a crocodile, then it indicates the direction in which this crocodile will run. Directions are indicated by the letters: "N" "- north, "S" "- south, "E" "- east, "W" "- west .Output
Format The
output file should contain a single number "- the maximum number of crocodiles that can be driven away without getting angry.
Example 1
Input
1 5
WN.SE
Output
4
Example 2
Input
1 3
EW
Output
0
Example 3
Input
3 4
.NW
WWSS
EWEW
Output
4 Can you please tell me
how to speed up the code? Part of the tests the code passes correctly, and the rest - TL (Time Limit). How to speed up code execution so that there is no 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.

Test the solution: https://contest.yandex.ru/roi/contest/999/enter

Answer 1

Try recursion.
You take the first crocodile that comes across (any). You look to see if there are others in his path and try to remove them, and so on until the very last. The most important thing is to provide looping handling as in the second example.
You should get something like
procedure TestCroco(row, col)
begin
if a[row, col] = 0 then Exit;
..............
end;
for row := 0 to rows - 1 do
for col := 0 to cols - 1 do
TestCroco(row, col);
PS I can make a fee for a nominal fee

Answer 2

You have a wrong, slow algorithm.
Every time you remove a crocodile, you look for a new crocodile all over the field, making all the checks. It's slow. You can check exactly once for each crocodile:
1) Number all the crocodiles. I recommend that in the new matrix write 0 for emptiness and the number of the crocodile, where there is one.
2) As you have already done, for all crocodiles in the right direction, look at all the cells, but do not stop at the first oncoming crocodile. Keep moving and count all the crocodiles you meet. In this way, for each crocodile, you will find out how many you need to drive away in front of him.
Right away, put all the crocodiles with a count of 0 (which can already be driven away right now) in a queue. Drive crocodiles out of the queue until it is empty. When processing such a crocodile - read it in the answer, erase it from the matrix, and, importantly, update the counters for all the crocodiles that it interfered with. To do this, walk from the current crocodile in ALL directions and, if the crocodile is walking towards you there and has not yet been removed, decrease its counter. If the counter becomes 0, add this crocodile to the queue. All.
This solution is in O(n^3) and yours is in O(n^4).
It turns out something like a breadth walk on the crocodile graph. It would be possible to calculate all the edges first (make lists of who interferes with whom), but these lists in total will occupy N ^ 3 memory, which may not fit into memory, but does not fundamentally affect the speed of work (well, it will speed up 4 times, somewhere - then). If again it doesn’t pass in time, but the cube fits in your memory, then build a graph and, when removing the crocodile, look not in the matrix for whom it interferes with, but already in the graph, go through the list of adjacent vertices.

Answer 3

You have a task on the subject of topological sorting: At the link stackoverflow.com/questions/4620100/partial-order-... there is a python code that stops as soon as everything is sorted. Those. when only cycles remain. So you need to implement something like this. The complexity seems to be O(sum of nodes + sum of graph edges). Plus the complexity of building the graph itself.