Submission #67456853

---

Source Code Expand

// 綺麗に解きなおし

#include <bits/stdc++.h>
using namespace std;

  /////////////////// メイン ///////////////////

int main() {
  
  //////////////////// 入力 ////////////////////

  int h, w;
  cin >> h >> w;

  // 文字列のvectorとしてグリッドを受け取る
  vector<string> maze(h);
  for (int i=0; i<h; i++){
    cin >> maze.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // 剰余類環の法
  int mod = 1e9+7;

  // 経路数を記録する二次元vector
  // counters.at(i).at(j)は、マス(i,j)への経路数
  // 壁の場合に楽ができるように0で初期化する
  vector<vector<int>> counters(h,vector<int>(w,0));

  // 二次元DP
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {

      // 壁マスだったら何もしない
      // 0で初期化してあるので、何もしなくていい
      if (maze.at(i).at(j)=='#') continue;

      // 左上のマスの場合
      if (i==0&&j==0) {

        // 明らかに1通り
        counters.at(i).at(j) = 1;

      // 上端列（左上以外）の場合
      } else if (i==0) {

        // すぐ左のマスから来るしかない
        counters.at(i).at(j) = counters.at(i).at(j-1);

      // 左端列（左上以外）の場合
      } else if (j==0) {

        // すぐ上のマスから来るしかない
        counters.at(i).at(j) = counters.at(i-1).at(j);

      // それ以外の場合
      } else {

        // 上から来るか左から来るかの和
        // 足し算のたびに剰余計算をしておく
        counters.at(i).at(j) = (counters.at(i-1).at(j)+counters.at(i).at(j-1))%mod;

      }

    }
  }
  
  // 答えは右下のマスの値
  result = counters.at(h-1).at(w-1);
  
  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result