#include #include using namespace std; using namespace atcoder; using ll = long long; #define rep(i, s, n) for(int i = s; i < (int)(n); i++) #define repr(i, s, n) for(int i = ((int)(n) - 1); i >= s; i--) int h, w, hw; vector di2 = {0, 1}, dj2 = {1, 0}; vector seen; vector a; #define ij_no(i, j) ((int) (i) * w + (int) (j)) // マス目の座標→通し番号 #define no_i(no) ((int) no / w) // 通し番号→ 座標i #define no_j(no) ((int) no % w) // 通し番号→ 座標j #define move2_i(i, d) ((int) i + di2[d]) // 2方向の移動後i座標 #define move2_j(j, d) ((int) j + dj2[d]) // 2方向の移動後j座標 bool frame_in(int ni, int nj, int h, int w){ if(0 <= ni && ni < h && 0 <= nj && nj < w) return true; else return false; } int move2_no(int no, int dir, int h, int w){ // 2方向の移動後no 枠外なら -1を返す int nxi = move2_i(no_i(no), dir), nxj = move2_j(no_j(no), dir); if(!frame_in(nxi, nxj, h, w)){ return -1; } else return ij_no(nxi, nxj); } void dfs(int v, int &ans, int &now){ if(v == hw - 1){ ans ++; return; } if(seen[v]) return; seen[v] = 1; if(a[v] == 'o') now ++; else if(a[v] == 'x') now --; if(now < 0) return ; rep(i, 0, 2){ int nx = move2_no(v, i, h, w); if(nx != -1 && a[nx] != '#') dfs(nx, ans, now); } seen[v] = 0; if(a[v] == 'o') now --; else if(a[v] == 'x') now ++; } int main(){ cin >> h >> w; hw = h * w; a.resize(hw); seen.assign(hw, 0); rep(i, 0, hw) cin >> a[i]; int ans = 0; int now = 0; dfs(0, ans, now); cout << ans << endl; }