#include #include using namespace std; const int MAX_H = 10; const int MAX_W = 10; int H, W; vector> grid; int count_paths = 0; void dfs(int i, int j, int gems) { // マス(i, j)が右下のマス(H-1, W-1)であり、かつ宝石を没収されない経路であれば、経路の数をインクリメントする if (i == H - 1 && j == W - 1 && gems >= 0) { count_paths++; return; } // マス(i, j)がグリッドの範囲内であり、かつ壁(#)でない場合 if (0 <= i && i < H && 0 <= j && j < W && grid[i][j] != '#') { // 右に進む if (j + 1 < W) { int new_gems = gems; if (grid[i][j + 1] == 'o') new_gems++; else if (grid[i][j + 1] == 'x') new_gems--; // 宝石が負の値になる場合は経路を無効にする if (new_gems >= 0) { dfs(i, j + 1, new_gems); } } // 下に進む if (i + 1 < H) { int new_gems = gems; if (grid[i + 1][j] == 'o') new_gems++; else if (grid[i + 1][j] == 'x') new_gems--; // 宝石が負の値になる場合は経路を無効にする if (new_gems >= 0) { dfs(i + 1, j, new_gems); } } } } int main() { cin >> H >> W; // グリッドの入力 grid.resize(H, vector(W)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { cin >> grid[i][j]; } } // 初期位置は(0, 0)で、宝石の初期個数は1つ dfs(0, 0, 1); cout << count_paths << endl; return 0; }