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コードで少しだけ変更すればよい.