빵집 (feat. 백준, 3109번)

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

3109번: 빵집

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int R, C;
char arr[10000][500];
bool func(register int r, register int c){
    arr[r][c] = 'x';
    if(c == C - 1)
        return true;
    if(r + 1 < R && arr[r + 1][c + 1] == '.' && func(r + 1, c + 1))   // 오른쪽 아래
        return true;
    if(arr[r][c + 1] == '.' && func(r, c + 1))        // 오른쪽
        return true;
    if(r - 1 >= 0 && arr[r - 1][c + 1] == '.' && func(r - 1, c + 1))  // 오른쪽 위
        return true;
    return false;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int ans = 0;
    cin >> R >> C;
    for(register int r = 0, c; r < R; ++r)
        for(c = 0; c < C; ++c)
            cin >> arr[r][c];
    for(register int r = R - 1; r >= 0; --r)
        if(func(r, 0))
            ++ans;
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

검사를 시작하는 행이 첫 행이기 때문에 오른쪽 상단부터 체크할 경우, 겹치는 구간이 최소화됩니다.

마찬가지로 검사를 시작하는 행이 마지막 행이라면 오른쪽 하단부터 체크해야 합니다.