3109번: 빵집

https://www.acmicpc.net/problem/3109


$O(RC)$

위에서부터 가능한 경로는 무조건 생성해야 가장 많이 만들 수 있다.
경로를 찾기 위해 1열의 모든 행, 위에서부터 시작하여 dfs를 돌린다.
다음 열의 위, 중간, 아래 순으로 탐색하고 한 번 탐색한 칸은 이후에 탐색하지 않는다.
이런식으로 탐색하다 가장 큰 열에 도착할 때마다 카운트 해주면 된다.

#include<stdio.h>
const int MAX_R = 1e4, MAX_C = 5e2;
int r, c, res;
char str[MAX_R][MAX_C + 1];
bool dfs(int x, int y) {
    if (x<0 || x == r || str[x][y] == 'x') return false;
    str[x][y] = 'x';
    if (y == c - 1) return true;
    return dfs(x - 1, y + 1) || dfs(x, y + 1) || dfs(x + 1, y + 1);
}
int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++) scanf("%s", str[i]);
    for (int i = 0; i < r; i++) res += dfs(i, 0);
    printf("%d", res);
    return 0;
}