この問題は単純な幅優先探索 (BFS) 等で時間計算量 \(O(NM(N+M))\) で正解できますが、今回はそれよりも高速な解法を示します。

今いるマス \(x\) とプレイヤーの直前の移動方向 ( 上・下・左・右・停止 ) とをペアにした \(5NM\) 個の頂点を考えます。
直前の移動方向「停止」はそのマスの上で停まれている状態を、その他の移動方向はそのマスの上をその向きに通過しようとしていることを表現しています。
この上で、以下の要領で移動を BFS します。 最初は ( マス \((2,2)\) , 停止 ) から始めます。

• 直前の移動方向が「停止」である場合

  • \(x\) の上隣のマスが 氷 である場合、 ( \(x\) の上隣のマス, 上 ) の頂点に移動可能である。
  • \(x\) の下隣のマスが 氷 である場合、 ( \(x\) の下隣のマス, 下 ) の頂点に移動可能である。
  • \(x\) の左隣のマスが 氷 である場合、 ( \(x\) の左隣のマス, 左 ) の頂点に移動可能である。
  • \(x\) の右隣のマスが 氷 である場合、 ( \(x\) の右隣のマス, 右 ) の頂点に移動可能である。

• 直前の移動方向が「停止」でない場合

  • その方向に移動を続けることを試みる。
  • もし、その方向に隣接するマス \(y\) が 氷 なら、移動方向を保持することしかできず、 ( \(y\) , 移動方向 ) の頂点に移動可能である。
  • もし、その方向に隣接するマス \(y\) が 岩 なら、今いるマスで停止することができる。よって、 ( \(x\) , 停止 ) の頂点に移動可能である。

この BFS により、通過または停止する 氷 のマスを全て列挙できます。
よって、時間計算量 \(O(NM)\) でこの問題に正解できます。

実装例 (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;
}