#include using i64 = long long; using u64 = unsigned long long; using u32 = unsigned; using u128 = unsigned __int128; using i128 = __int128; const int dx[] = {1, 0}; const int dy[] = {0, 1}; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int H, W; std::cin >> H >> W; std::vector adj(H); std::vector> vis(H, std::vector(W)); for (int i = 0; i < H; i++) { std::cin >> adj[i]; } int ans = 0; auto dfs = [&](auto&& self, int i, int j, int cur) -> void { vis[i][j] = 1; if (i == H - 1 && j == W - 1) { if (cur >= 0) ans++; //! ??????????????????ans++ } //! ???????? //! 1.????????????????return??????????????? //! 2.????x???????x???cur==0?????? for (int d = 0; d < 2; d++) { int a = i + dx[d]; int b = j + dy[d]; if (a >= 0 && a < H && b >= 0 && b < W) { if (vis[a][b]) continue; if (adj[a][b] == '#') continue; if (adj[a][b] == 'x') { if (cur > 0) { self(self, a, b, cur - 1); } } else { self(self, a, b, cur + 1); } } } vis[i][j] = 0; }; dfs(dfs, 0, 0, 1); std::cout << ans << '\n'; return 0; }