SRM530 Div1 Medium

500
0からN-1に行くために使える辺の数 - 0からN-1に行くために使える頂点の数 + 2
解いてからしばらくたっていて、どうやってこの解にたどり着いたか覚えてない。twitterで解説してるつぶやきを見て解いたような・・・。
とりあえず、復習。

class GogoXMarisaKirisima {
public:
  int solve(vector <string> C) 
  {
    const int V = C.size();
    bool g[V][V];
    
    for (int i = 0; i < V; ++i) {
      for (int j = 0; j < V; ++j) {
        g[i][j] = C[i][j] == 'Y';
      }
      g[i][i] = 'Y';
    }
    for (int k = 0; k < V; ++k) {
      for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
          g[i][j] = g[i][j] || (g[i][k] && g[k][j]);
        }
      }
    }    

    int M = 0;
    int N = 0;
    for (int i = 0; i < V; ++i) {
      if(g[0][i] && g[i][V - 1]) ; else continue;
      ++N;
      for (int j = 0; j < V; ++j) {
        M += g[0][j] && g[j][V - 1] && C[i][j] == 'Y';
      }
    }

    if (N == 0) return 0;
    return M - N + 2;
  }

};