빵집

*true면 파이프 설치 가능함. 아니면 가능하지 않는 구간 

#include <iostream>
#include <vector>
#include <queue>
 
#define MAXR 10001
#define MAXC 501
using namespace std;
 
int r, c, ans = 0;
char map[MAXR][MAXC];
bool visited[MAXR][MAXC];
int dx[3] = {-1, 0, 1}, dy[3] = {1, 1, 1};
typedef pair<int, int> pp;
void print()
{
    cout << '\n';
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (visited[i][j]) cout << 1 << ' ';
            else cout << 0 << ' '; 
            
        }
        cout << '\n';
    }
    cout << '\n';
}
 
bool dfs(int row, int col) {
    visited[row][col] = true;
    
    if (col == 0 && map[row][1] == 'x') {
        return false;
    }
    if (col == c-1) {
        ans++;
        return true;
    }
 
    for (int i = 0; i < 3; i++) {
        int nx = row + dx[i];
        int ny = col + dy[i];
 
        if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny] || map[nx][ny] == 'x') continue;
 
        if (dfs(nx, ny)) return true;
 
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> map[i][j];
        }
    }
    //첫 열과 마지막열은 각각 빵집과 원웅이의 빵집이다.
    for (int i = 0; i < r; i++) 
        dfs(i,0);
    cout << ans << '\n';
    return 0;
}