#include #include using namespace std; using namespace atcoder; using ll = long long; using ld = long double; int h, w; string a[11]; int dx[2] = {1, 0}; int dy[2] = {0, 1}; int ans = 0; int main() { cin >> h >> w; for (int i = 0; i < h; i++) cin >> a[i]; queue> que; que.push({0, 1}); while (!que.empty()) { auto [p, q] = que.front(); que.pop(); int x = p / w; int y = p % w; //cout << x << ' ' << y << ' ' << q << endl; if (x == h - 1 && y == w - 1) { ans++; continue; } for (int i = 0; i < 2; i++) { int r = q; int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= h || ny >= w || a[nx][ny] == '#') continue; if (a[nx][ny] == 'o') r++; else if (a[nx][ny] == 'x') r--; if (r >= 0) que.push({nx * w + ny, r}); } } cout << ans << endl; return 0; }