M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) D - Weak Takahashi

問題の要約
　縦H行、横W行のH*Wマスからなるグリッドがある。上からi行目、左からj列目のマスを(i,j)と表す。
　各マスの状態は文字Ci,jで表され、Ci,j=.ならばマス(i,j)は空きマスであり、Ci,j=#ならばマス(i,j)は壁である。
　今、グリッド上を歩こうとしている。マス(i,j)にいるとき、マス(i,j+1)またはマス(i+1,j)に移動することができる。
　ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできない。移動することのできるマスがなくなった時点で立ち止まる。
　マス(1,1)から歩き始めるとき、立ち止まるまでに通ることのできるマスは最大で何マスか?
制約
　1<=H,W<=100
入力
　H W
　C1,1 ... C1,W
　...
　CH,1 ... CH,W
考え方
　1,マス(i,j)からマス(i,j+1)かマス(i+1,j)にしか移動できないので、すべてのマスが空マスの場合、最下段か左端に行く。
　　条件分岐を単純化するために、最下段と左端に壁を作る。
　2,再帰関数を作る。
　3,ただの再帰だとTLEなのでメモ化する。

実際のプログラム
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int ans;
vector<vector<int>> memo;

void f(vector<string> C, int i, int j, int weak){
  if(C[i][j] == '#'){
    return;
  }else{
    memo[i][j] = weak;
    ans = max(ans,weak);
  }
  if(memo[i+1][j] == -1){
    f(C,i+1,j,weak+1);
  }
  if(memo[i][j+1] == -1){
    f(C,i,j+1,weak+1);
  }
}

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> C(H+1);
  for(int i = 0; i < H; i++){
    cin >> C[i];
    C[i] += "#";
  }
  for(int i = 0; i < W+1; i++){
    C[H] += "#";
  }
  
  ans = 0;
  memo.resize(H+1,vector<int>(W+1,-1));
  f(C,0,0,1);
  
  cout << ans << endl;
  
  return 0;
}