While this problem can be solved with a simple Breadth-First Search (BFS) in a total of \(O(NM(N+M))\) time, we introduce a faster solution here.

Consider \(5NM\) vertices labeled by pairs of current square \(x\) and the last direction of the player’s move (up, down, left, right, or stop).
If the last direction is “stop”, it means that the player is stopping on the square; the other directions mean that the player is about to pass through the square on that direction.
On this graph, we do BFS for the paths. Initially, we start with (square \((2, 2)\), stop)>

• If the last direction is “stop”:

  • If the square right above \(x\) is ice, you can move to the vertex (square above \(x\), up).
  • If the square right below \(x\) is ice, you can move to the vertex (square below \(x\), down).
  • If the square next to \(x\) in the left is ice, you can move to the vertex (square left to \(x\), left).
  • If the square next to \(x\) in the right is ice, you can move to the vertex (square right to \(x\), right).

• If the last direction is not “stop”:

  • Try to move in that direction.
  • If the adjacent square \(y\) in that direction is ice, you can just keep moving in that direction, so you can move to the vertex (\(y\), current direction).
  • If the adjacent square \(y\) in that direction is rock, you can stop at the current square, so you can move to the vertex (\(y\), stop).

By this BFS, you can enumerate all the “ice” squares that you can pass through or rest.
Hence, the problem can be solved in a total of \(O(NM)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> s(n);
  for(auto &nx : s){cin >> nx;}

  vector<int> fl(5*n*m,0);
  queue<int> q;
  fl[5*(m+1)+4]=1;
  q.push(5*(m+1)+4);
  while(!q.empty()){
    int od=q.front();q.pop();
    int x=(od/5)/m;
    int y=(od/5)%m;
    int d=od%5;

    if(d==4){
      // stop
      for(int i=0;i<4;i++){
        int nx=x+dx4[i];
        int ny=y+dy4[i];
        int nd=i;
        if(s[nx][ny]=='.'){
          int nid=5*(nx*m+ny)+nd;
          if(fl[nid]==0){
            fl[nid]=1;
            q.push(nid);
          }
        }
      }
    }
    else{
      // keep the direction
      int nx=x+dx4[d];
      int ny=y+dy4[d];
      int nd=d;
      if(s[nx][ny]=='.'){
        int nid=5*(nx*m+ny)+nd;
        if(fl[nid]==0){
          fl[nid]=1;
          q.push(nid);
        }
      }
      else{
        // hit a rock
        int nid=5*(x*m+y)+4;
        if(fl[nid]==0){
          fl[nid]=1;
          q.push(nid);
        }
      }
    }
  }

  int res=0;
  for(int i=0;i<n*m;i++){
    res+=max({fl[5*i],fl[5*i+1],fl[5*i+2],fl[5*i+3],fl[5*i+4]});
  }
  cout << res << "\n";
  return 0;
}