3184-正-DFS


質問する



質問リンク:https://www.acmicpc.net/problem/3184

ポリシー

  • は水平と垂直のみから判断します.
  • どうせすべての分野は垣根で囲まれていて、それぞれの分野は羊と狼の個数を漏らすだけでいいです.
  • R,C<=250,DFSによる確認時間で十分です.
  • コード#コード#

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int R, C;
    char a[252][252];
    int wCnt =0, sCnt=0;
    int wCntTotal =0, sCntTotal=0;
    // 가로 세로 이동을 위한 배열
    int dy[4] = {-1, 0, 1, 0};
    int dx[4] = {0, 1, 0, -1};
    
    void DFS(int r, int c){
        // 늑대, 양에 따라 수를 늘려준다.
        if(a[r][c] == 'v') wCnt++;
        else if(a[r][c] == 'o') sCnt++;
        // 이후 한번 지나간 영역은 울타리로 바꿔주어 중복체크를 피한다. 
        a[r][c] = '#';
    
        for(int i=0; i<4; i++){
            int rr = r+dy[i];
            int cc = c+dx[i];
    
            if(a[rr][cc] != '#'){
                DFS(rr,cc);
            }
        }
    }
    
    int main(){
        ios_base::sync_with_stdio(false);
        // freopen("../input.txt","rt",stdin);
        
        memset(a, '#', sizeof(a));
        cin >> R >> C;
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                cin >> a[i][j];
            }
        }
    
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                if(a[i][j] != '#'){
                    DFS(i,j);
                    if(wCnt >= sCnt) sCnt = 0;
                    else if(wCnt < sCnt) wCnt = 0;
                    wCntTotal += wCnt;
                    sCntTotal += sCnt;
                    wCnt = sCnt = 0;
                }
            }
        }
        cout<<sCntTotal << " "<< wCntTotal<<'\n';
        return 0;
    }
    
    
    

    感想


    一つの分野では、羊の数と狼の数を把握すればいい.既存のDFSコードで少しだけ変更すればよい.